2020-2021:teams:namespace:牛客多校第八场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:牛客多校第八场 [2020/08/08 16:35] great_designer [I] |
2020-2021:teams:namespace:牛客多校第八场 [2020/08/08 20:55] (当前版本) great_designer |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| 参考题解的答案是：总点数-#（k个点， k-1条边的连通分量） | 参考题解的答案是：总点数-#（k个点， k-1条边的连通分量） | ||
| - | |||
| - | |||
| <hidden> | <hidden> | ||
| 行 102: | 行 100: | ||
| </code> | </code> | ||
| </hidden> | </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/牛客多校第八场.1596875721.txt.gz · 最后更改: 2020/08/08 16:35 由 great_designer
