2020-2021:teams:namespace:牛客多校第八场
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:牛客多校第八场 [2020/08/03 16:48] great_designer 创建 |
2020-2021:teams:namespace:牛客多校第八场 [2020/08/08 20:55] (当前版本) great_designer |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| 所以预计本周周报将陷入无题可写的困境。 | 所以预计本周周报将陷入无题可写的困境。 | ||
| + | |||
| + | |||
| + | =====I===== | ||
| + | |||
| + | 比赛时以为是二分图的匹配用匈牙利算法做了，搞了半天搞出来了但是复杂度太高了过不去。 | ||
| + | |||
| + | 参考题解的答案是：总点数-#（k个点， k-1条边的连通分量） | ||
| + | |||
| + | <hidden> | ||
| + | <code C> | ||
| + | #include<stdio.h> | ||
| + | #include<string.h> | ||
| + | |||
| + | #include<vector> | ||
| + | #include<algorithm> | ||
| + | |||
| + | using namespace std; | ||
| + | |||
| + | bool vis[200020]; | ||
| + | int F[200020]; | ||
| + | |||
| + | void init() | ||
| + | { | ||
| + | memset(F,-1,sizeof(F)); | ||
| + | memset(vis,0,sizeof(vis)); | ||
| + | } | ||
| + | |||
| + | int find(int x) | ||
| + | { | ||
| + | if(F[x]==-1) | ||
| + | { | ||
| + | return x; | ||
| + | } | ||
| + | return F[x]=find(F[x]);//改了根 | ||
| + | } | ||
| + | |||
| + | void bing(int x,int y) | ||
| + | { | ||
| + | int t1=find(x);//找到x的根 | ||
| + | int t2=find(y);//找到y的根 | ||
| + | if(t1==t2) | ||
| + | { | ||
| + | vis[t1]=1;//同一个根，该根变1 | ||
| + | return; | ||
| + | } | ||
| + | F[t1]=t2;//如果x和y的根不同，修改t1的根t2 | ||
| + | if(vis[t1]) | ||
| + | { | ||
| + | vis[t2]=1; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | int t; | ||
| + | scanf("%d",&t); | ||
| + | int k=0; | ||
| + | while(t--) | ||
| + | { | ||
| + | k++; | ||
| + | init(); | ||
| + | int n; | ||
| + | scanf("%d",&n); | ||
| + | vector<int> a(n),b(n); | ||
| + | vector<int> val; | ||
| + | int i; | ||
| + | for(i=0;i<n;i++) | ||
| + | { | ||
| + | scanf("%d%d",&a[i],&b[i]); | ||
| + | val.push_back(a[i]); | ||
| + | val.push_back(b[i]); | ||
| + | } | ||
| + | sort(val.begin(),val.end()); | ||
| + | int tot=unique(val.begin(),val.end())-val.begin(); | ||
| + | val.resize(tot); | ||
| + | for(i=0;i<n;i++) | ||
| + | { | ||
| + | a[i]=lower_bound(val.begin(),val.end(),a[i])-val.begin(); | ||
| + | b[i]=lower_bound(val.begin(),val.end(),b[i])-val.begin(); | ||
| + | bing(a[i],b[i]); | ||
| + | } | ||
| + | int ans=tot; | ||
| + | for(i=0;i<tot;i++)//遍历c中不同的点 | ||
| + | { | ||
| + | if(F[i]==-1&&!vis[i]) | ||
| + | { | ||
| + | ans--; | ||
| + | } | ||
| + | } | ||
| + | printf("Case #%d: %d\n",k,ans); | ||
| + | } | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | =====G===== | ||
| + | |||
| + | 看代码觉得这个题明明没有描述的那么难啊…… | ||
| + | |||
| + | <hidden> | ||
| + | <code C> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | #include<string.h> | ||
| + | |||
| + | int a[300][5]; | ||
| + | char s[100]; | ||
| + | |||
| + | char check(int x,int y,int z) | ||
| + | { | ||
| + | if((x==y&&x==z&&y==z)||(x!=y&&x!=z&&y!=z)||x==-1||y==-1||z==-1) | ||
| + | { | ||
| + | return 1; | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | int t,n,top; | ||
| + | scanf("%d",&t); | ||
| + | int kk=0; | ||
| + | while(t--) | ||
| + | { | ||
| + | kk++; | ||
| + | scanf("%d",&n); | ||
| + | int i; | ||
| + | for(i=1;i<=n;i++) | ||
| + | { | ||
| + | scanf("%s",s); | ||
| + | top=0; | ||
| + | int j; | ||
| + | for(j=0;j<strlen(s);j++) | ||
| + | { | ||
| + | if(s[j]=='[') | ||
| + | { | ||
| + | if(s[j+1]=='*') | ||
| + | { | ||
| + | a[i][top++]=-1; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | a[i][top++]=s[j+2]-'a'; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | char flag = 0; | ||
| + | printf("Case #%d: ",kk); | ||
| + | for(i=1;i<=n;i++) | ||
| + | { | ||
| + | if(flag) | ||
| + | { | ||
| + | break; | ||
| + | } | ||
| + | int j; | ||
| + | for(j=i+1;j<=n;j++) | ||
| + | { | ||
| + | if(flag) | ||
| + | { | ||
| + | break; | ||
| + | } | ||
| + | int k; | ||
| + | for(k=j+1;k<=n;k++) | ||
| + | { | ||
| + | if(flag) | ||
| + | { | ||
| + | break; | ||
| + | } | ||
| + | char hv=1; | ||
| + | int d; | ||
| + | for(d=0;d<4;d++) | ||
| + | { | ||
| + | if(!check(a[i][d],a[j][d],a[k][d])) | ||
| + | { | ||
| + | hv=0; | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | if(hv) | ||
| + | { | ||
| + | printf("%d %d %d\n",i,j,k); | ||
| + | flag=1; | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | if(!flag) | ||
| + | { | ||
| + | puts("-1"); | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | =====K===== | ||
| + | |||
| + | 本来在赛场上我已经几乎把这个题分析完了，只是觉得维护太麻烦，可能会用到线段树之类（不会），就没写。 | ||
| + | |||
| + | 然后看到这份代码，觉得这就是个暴力…… | ||
| + | |||
| + | <hidden> | ||
| + | <code C> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | |||
| + | int T; | ||
| + | long long Max[101000]; | ||
| + | long long a[101000]; | ||
| + | int b[101000]; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | scanf("%d",&T); | ||
| + | int tt; | ||
| + | for(tt=1;tt<=T;tt++) | ||
| + | { | ||
| + | int n; | ||
| + | scanf("%d",&n); | ||
| + | long long now = 0; | ||
| + | Max[0] = -1e10; | ||
| + | int i; | ||
| + | for(i = 1; i <= n; i++) | ||
| + | { | ||
| + | scanf("%lld", &a[i]); | ||
| + | now += a[i];//前缀和 | ||
| + | Max[i]=Max[i-1]>now?Max[i-1]:now;//求当前最大利润 | ||
| + | } | ||
| + | unsigned long long ans1 = 0, ans2 = 0;//开两个的原因是unsigned long long不能出现负数，为了解决用两个unsigned long long来存值，一个存负值，一个存正值 | ||
| + | int w; | ||
| + | for(i = 1; i <= n + 1; i++) | ||
| + | { | ||
| + | if(i <= n) | ||
| + | { | ||
| + | scanf("%d", &b[i]); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | b[i] = 0; | ||
| + | } | ||
| + | if(i == 1) | ||
| + | { | ||
| + | w = b[1]; | ||
| + | } | ||
| + | if(b[i] < w) | ||
| + | { | ||
| + | if(Max[i - 1] < 0) | ||
| + | { | ||
| + | ans2 += (unsigned long long)(-Max[i - 1]) * (w - b[i]); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | ans1 += (unsigned long long)Max[i - 1] * (w - b[i]); | ||
| + | } | ||
| + | w = b[i];//用了w-b[i]个，剩下了b[i]个，最后有个b[n+1]=0收尾，不重不漏 | ||
| + | } | ||
| + | } | ||
| + | if(ans1 < ans2) | ||
| + | { | ||
| + | printf("Case #%d: %d -%llu\n", tt, b[1], ans2 - ans1); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | printf("Case #%d: %d %llu\n", tt, b[1], ans1 - ans2); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
2020-2021/teams/namespace/牛客多校第八场.1596444481.txt.gz · 最后更改: 2020/08/03 16:48 由 great_designer
