2018 ACM 网络选拔赛 沈阳赛区
2024-10-18 18:20:17
B. Call of Accepted
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=1e2+; /**
+ - 3
* / 2
d 1
( ) 0
**/ int xl[maxn],xr[maxn],y[maxn];
char s[maxn],z[maxn]; int main()
{
int len,i,g1,g2,a,b,c,d,sym;
while (~scanf("%s",s))
{
len=strlen(s);
g1=;
g2=;
y[]=inf;
for (i=;i<len;i++)
if (s[i]>='' && s[i]<='')
{
g1++;
xl[g1]=;
while (s[i]>='' && s[i]<='')
{
xl[g1]=xl[g1]*+s[i]-;
i++;
}
i--;
xr[g1]=xl[g1];
}
else
{
switch(s[i])
{
case '(':
sym=;
break;
case ')':
sym=;
break;
case 'd':
sym=;
break;
case '*':
sym=;
break;
case '/':
sym=;
break;
case '+':
sym=;
break;
case '-':
sym=;
break;
}
while (y[g2]<=sym || s[i]==')')
{
switch(z[g2])
{
case 'd':
///ldr l>=0,r>=1,else illegal
///正数，负数
xl[g1-]=max(,xl[g1-]);
xl[g1]=max(,xl[g1]);
xr[g1-]*=xr[g1];
break;
case '+':
xl[g1-]+=xl[g1];
xr[g1-]+=xr[g1];
break;
case '-':
xl[g1-]-=xr[g1];
xr[g1-]-=xl[g1];
break;
case '*':
a=xl[g1-]*xl[g1];
b=xl[g1-]*xr[g1];
c=xr[g1-]*xl[g1];
d=xr[g1-]*xr[g1];
xl[g1-]=min(min(a,b),min(c,d));
xr[g1-]=max(max(a,b),max(c,d));
break;
case '/':
a=xl[g1-]/xl[g1];
b=xl[g1-]/xr[g1];
c=xr[g1-]/xl[g1];
d=xr[g1-]/xr[g1];
xl[g1-]=min(min(a,b),min(c,d));
xr[g1-]=max(max(a,b),max(c,d));
break;
case '(':
break;
}
if (z[g2]=='(')
break;
g2--;
g1--;
}
if (s[i]==')')
g2--;
else
{
y[++g2]=sym;
z[g2]=s[i];
}
} while (g2!=)
{
switch(z[g2])
{
case 'd':
xr[g1-]*=xr[g1];
break;
case '+':
xl[g1-]+=xl[g1];
xr[g1-]+=xr[g1];
break;
case '-':
xl[g1-]-=xr[g1];
xr[g1-]-=xl[g1];
break;
case '*':
a=xl[g1-]*xl[g1];
b=xl[g1-]*xr[g1];
c=xr[g1-]*xl[g1];
d=xr[g1-]*xr[g1];
xl[g1-]=min(min(a,b),min(c,d));
xr[g1-]=max(max(a,b),max(c,d));
break;
case '/':
a=xl[g1-]/xl[g1];
b=xl[g1-]/xr[g1];
c=xr[g1-]/xl[g1];
d=xr[g1-]/xr[g1];
xl[g1-]=min(min(a,b),min(c,d));
xr[g1-]=max(max(a,b),max(c,d));
break;
case '(':
break;
}
g2--;
g1--;
} printf("%d %d\n",xl[],xr[]);
} return ;
}
/*
3*(2d3)
1+1d2d3d4d5+2 (2d3)*(1+3*3d4)d5 (2+(3*4+5d1d3)d2)d3 (10-30)*3d4 (10-3d4)*2d3 (10-3d4)*(10-3d4) (10-5d5)*(10-5d5) 3d(10-3d4)
3d(10-3d4)d(10-3d4)
*/
D. Made In Heaven
F. Fantastic Graph
详细题解：https://blog.csdn.net/qq_40993793/article/details/82626562
判断是否存在可行流（满足下界条件）：
汇点T -> 源点S inf(如果有流，则源源不断增加)
超级源点SS -> 超级汇点TT 判断是否满流，值为点TT的入度
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
const int maxn=4e3+;
const int inf=1e9; struct node
{
int d,len;
node *next,*opp;
}*e[maxn]; int sum=,s,t;
int q[maxn],dep[maxn];
bool vis[maxn]; void add_edge(int x,int y,int len)
{
node *p1=(node*) malloc (sizeof(node));
node *p2=(node*) malloc (sizeof(node)); p1->d=y;
p1->len=len;
p1->next=e[x];
p1->opp=p2;
e[x]=p1; p2->d=x;
p2->len=;
p2->next=e[y];
p2->opp=p1;
e[y]=p2;
} bool bfs()
{
int head=,tail=,d,dd;
node *p;
memset(vis,,sizeof(vis));
vis[s]=;
dep[s]=;
q[]=s; while (head<tail)
{
head++;
d=q[head];
p=e[d];
while (p)
{
dd=p->d;
if (p->len> && !vis[dd])
{
tail++;
q[tail]=dd;
vis[dd]=;
dep[dd]=dep[d]+;
}
p=p->next;
}
}
if (vis[t])
return ;
return ;
} int dfs(int d,int add)
{
if (!add || d==t)
return add;
int totf=,f,dd;
node *p=e[d];
while (p)
{
dd=p->d;
if (dep[dd]==dep[d]+ && (f=dfs(dd,min(add,p->len)))>)
{
totf+=f;
add-=f;///зЂвт
p->len-=f;
p->opp->len+=f;
}
p=p->next;
}
return totf;
} int main()
{
int n,m,k,l,r,x,y,i,T=; while (~scanf("%d%d%d",&n,&m,&k))
{
scanf("%d%d",&l,&r);
s=n+m+,t=n+m+;
for (i=;i<=t;i++)
e[i]=NULL; for (i=;i<=n;i++)
add_edge(n+m+,i,l);
add_edge(,n+m+,l*n);
for (i=;i<=n;i++)
add_edge(,i,r-l); add_edge(n+m+,n+m+,l*m);
for (i=n+;i<=n+m;i++)
add_edge(i,n+m+,l);
for (i=n+;i<=n+m;i++)
add_edge(i,n+m+,r-l); add_edge(n+m+,,inf); while (k--)
{
scanf("%d%d",&x,&y);
add_edge(x,n+y,);
} sum=;
while (bfs())
sum+=dfs(s,inf);
printf("Case %d: ",++T);
if (sum==(n+m)*l)
printf("Yes\n");
else
printf("No\n");
}
return ;
}
G. Spare Tire
I. Lattice's basics in digital electronics
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=1e5+; int tr[];
char s1[*],s2[*],s3[*],s4[*];
char s[*]; int main()
{
int t,m,n,a,i,j,k,len,now,g,value;
scanf("%d",&t);
while (t--)
{
memset(tr,,sizeof(tr));
scanf("%d%d",&m,&n);
for (i=;i<=n;i++)
{
scanf("%d%s",&a,s);
len=strlen(s);
k=;
for (j=;j<len;j++)
k=(k<<)+s[j]-;
tr[k]=a;
} scanf("%s",s1);
len=strlen(s1);
j=;
for (i=;i<len;i++)
{
if (s1[i]>='' && s1[i]<='')
value=s1[i]-;
else if (s1[i]>='A' && s1[i]<='F')
value=s1[i]-;
else
value=s1[i]-; s2[j++]=value/+;
value%=;
s2[j++]=value/+;
value%=;
s2[j++]=value/+;
value%=;
s2[j++]=value+;
}
s2[j]='\0';
len=j; now=;
for (i=;i<len/;i++)
{
g=;
j=i*;
for (k=j;k<j+;k++)
g+=s2[k]-;
if ((g+)%==s2[k]-)
{
for (k=j;k<j+;k++)
s3[now++]=s2[k];
}
}
s3[now]='\0'; j=;
len=;
for (i=;i<now;i++)
{
j=j*+s3[i]-;
if (j>)
continue;
if (tr[j])
{
s4[len++]=tr[j];
if (len==m)
break;
j=;
}
}
s4[len]='\0';
printf("%s\n",s4);
}
return ;
}
/*
10
8 3
49 0001
50 01001
51 011
14DB24722698 2
15 9
32 0100
33 11
100 1011
101 0110
104 1010
108 00
111 100
114 0111
119 0101
908 100
100 2
65 010
66 1011
AAAAAA
*/
K. Supreme Number
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=1e5+; typedef pair<int,int> P; char str[maxn];
int g=,b,a[maxn];
int c[]={,,,,};
int shi[]; bool prime(int t)
{
int i;
for (i=;i<=sqrt(t);i++)
if (t%i==)
return ;
return ;
} void dfs(int s,int w,vector<P>v)
{
vector<P>::iterator j;
vector<P>vv;
int t,i; for (i=;i<;i++)
{ // if (shi[w]*c[i]+s==711)
// printf("z"); for (j=v.begin();j!=v.end();j++)
{
if (!prime(j->first+shi[j->second]*c[i]))
break;
} if (j==v.end())
{
t=shi[w]*c[i]+s;
vv.clear();
for (j=v.begin();j!=v.end();j++)
{
vv.push_back(make_pair(j->first,j->second));
vv.push_back(make_pair(j->first+shi[j->second]*c[i],j->second+));
}
vv.push_back(make_pair(c[i],)); // printf("%d:\n",t);
// for (j=vv.begin();j!=vv.end();j++)
// printf("%d\n",j->first); g++;
a[g]=t;
dfs(t,w+,vv);
}
}
} int main()
{
vector<P>v;
int t,T,i;
// cout<<pow(10,0)<<endl;
// cout<<pow(10,1)<<endl;
// cout<<pow(10,2)<<endl;
//
// printf("\n");
//
// printf("%f\n",pow(10,0));
// printf("%f\n",pow(10,1));
// printf("%f\n",pow(10,2));
//
// printf("\n");
//
// printf("%d\n",pow(10,0));
// printf("%d\n",pow(10,1));
// printf("%d\n",pow(10,2));
//
// printf("\n");
//
// printf("%d\n",(int)pow(10,0));
// printf("%d\n",(int)pow(10,1));
// printf("%d\n",(int)pow(10,2));
//
// printf("\n");
//
// printf("\n");
//
// printf("%f\n",log(2)/log(2));
// printf("%f\n",log(4)/log(2));
// printf("%f\n",log(8)/log(2));
// printf("%f\n",log(16)/log(2));
//
// printf("%d\n",(int)(log(2)/log(2)));
// printf("%d\n",(int)(log(4)/log(2)));
// printf("%d\n",(int)(log(8)/log(2)));
// printf("%d\n",(int)(log(16)/log(2)));
//
// printf("\n");
//
// printf("%d\n",(int)log(2)/log(2));
// printf("%d\n",(int)log(4)/log(2));
// printf("%d\n",(int)log(8)/log(2));
// printf("%d\n",(int)log(16)/log(2));
// return 0; shi[]=;
for (i=;i<=;i++)
shi[i]=shi[i-]*; v.push_back(make_pair(,));
dfs(,,v);
sort(a+,a+g+); // for (i=1;i<=g;i++)
// printf("%d ",a[i]); scanf("%d",&t);
for (T=;T<=t;T++)
{
scanf("%str",str);
if (strlen(str)>)
{
printf("Case #%d: %d\n",T,a[g]);
continue;
}
b=atoi(str);
for (i=g;i>=;i--)
if (b>=a[i])
break;
printf("Case #%d: %d\n",T,a[i]);
}
return ;
}
最新文章
- 面向对象（五）super
- 8.31 js基础总结1
- Disciz!NT开源资源汇总
- cantor三分集
- SPServices.SPDisplayRelatedInfo
- 在opencv3中的机器学习算法练习：对OCR进行分类
- TYVJ P1088 treat Label：鞭笞人的DP
- 自动登录 登陆成功那个alert遮盖一直存在bug
- [SSH 2] 以网站主页面浅谈Struts2配置
- iOS H5容器的一些探究（一）：UIWebView和WKWebView的比较和选择
- DTCMS一些问题
- insert into (select...WITH CHECK OPTION) values(...)
- 自定义异常以及runtime类
- 固定DIV样式
- yii中常用路径<转>
- Tree 使用方式
- 新学了一个用python编写的简单的百度贴吧帖子的爬虫
- Android 百度地图开发问题----解决地图有时候加载不出来问题
- Redis集群伸缩
- hMailServer安装汉化方法
热门文章
- 【CV】ICCV2015_Unsupervised Visual Representation Learning by Context Prediction
- 《Linux内核分析》期终总结&《Linux及安全》期中总结
- hash函数补分博客
- bate版说明书
- [福大软工] Z班——Beta现场答辩反馈
- PAT 1009 说反话
- [转帖]Gartner预测2019年全球IT支出将达到3.8万亿美元
- Windows查看端口被什么进程占用的简单方法----菜鸟养成
- Node 开启
- width() 、 height() 方法；innerWidth() 、innerHeight() 方法；outerWidth() 、 outerHeight() 方法的区别