首页 > 代码库 > Codeforces Round #372 +#373 部分题解

Codeforces Round #372 +#373 部分题解

用了两场比赛上Div 1感觉自己好腊鸡的说。。。以下是这两场比赛的部分题解(不得不说有个黄学长来抱大腿还是非常爽的)

Round #372 :

Div 2 A:Crazy Computer

题意:给定N个输入和一个时间长度M,每次输入屏幕上增加一个字符,若两个输入间隔大于M则屏幕上的字符会被清空,问结束时屏幕上还有多少个字符

直接模拟没有什么好说的

代码:

技术分享
 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int main(){ 7     int n,c; 8     scanf("%d%d",&n,&c); 9     int last=0,cnt=0;10     for (int i=1;i<=n;i++) {11         int x;12         scanf("%d",&x);13         if (x-last>c) cnt=0;14         last=x;cnt++;15     }16     printf("%d\n",cnt);17     return 0;18 }
Crazy Computer
 Div 2 B:Complete the Word 

题意:给定一个字符串,其中某些字符未知,要求给出一个可能的字符串,使得存在一个包含26个大写字母的长度为26的连续子串

这题也是直接乱搞吧大概,我的思路就是统计每个子串中是否有重复,没有就说明合理然后随便构造一个答案就行了

代码:

技术分享
 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 char s[50100]; 7 int a[30],n; 8 int cnt=0; 9 int main(){10     scanf("%s",s+1);11     int n=strlen(s+1);12     int l=1;13     int cnt=0;14     for (int i=1;i<=n;i++){15         if (s[i]==?) {16             cnt++;17         }else {18             int t=s[i]-A+1;19             if (a[t]==1) {20                 while (s[i]!=s[l]) {21                     if (s[l]==?) {22                         cnt--;23                     }else a[s[l]-A+1]--;24                     l++;25                 }26                 if (s[l]==?) cnt--;27                 else a[s[l]-A+1]--;28                 l++;29             }30             a[t]++;31         }32         if (i-l+1==26) {33             for (int j=1;j<l;j++) printf("%c",s[j]==??A:s[j]);34             for (int j=l;j<=i;j++) {35                 if (s[j]!=?) printf("%c",s[j]);36                 else {37                     for (int k=1;k<=26;k++) {38                         if (a[k]) continue;39                         printf("%c",k+A-1);40                         a[k]++;41                         break;42                     }43                 }44             }45             for (int j=i+1;j<=n;j++) printf("%c",s[j]==??A:s[j]);46             return 0;47         }48     }49     printf("-1\n");50     return 0;51 }
Complete the Word

Div 2 C and Div 1 A:Plus and Square Root

题意:给定一个数和两个操作,一个操作为+k,另一个操作为开根号然后k=k+1,初始时数为1,k=1,求达到k=n+1时的操作数

考虑构造一个可行方案,设执行开方操作后那个数为t,那么有$t=mk,m\in \mathbb N$(若不满足则下一次无法开方)同时考虑开方操作前有$t^2=n(k-1),n \in \mathbb N$所以令$t=k(k-1)$ 即可

代码:

技术分享
 1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 typedef long long ll; 7 ll n,x; 8 int main(){ 9 cin>>n;10 x=2;11 for (ll i=1;i<=n;i++) {12     ll ans=(i+1)*(i+1)*i-x/i;13     cout<<ans<<endl;14     x=i*(i+1);15 }16 17 }
Plus and Square Root

Div 2 D and Div 1 B:Complete The Graph

题意:给定一张图,其中某些边的长度未知,求是否存在一种方案,使得最短路为L

先分层建图,求出经过k条未知边的最短路,然后从经过未知边数从小到大开始处理,直接构造出经过k条未知边,最短路为L的路径,可以得出,若无法构造出小于k条未知边的最短路为L的路径,那么该构造方式不会出现更短的路径。

这道题在考试时没秒出来,考完才发现写成大根堆+构图构太大MLE了囧。。。(不然说不定一场DIV 1了哼~)

代码:

技术分享
  1 #include<cstdio>  2 #include<iostream>  3 #include<cstring>  4 #include<algorithm>  5 #include<queue>  6 using namespace std;  7 typedef long long ll;  8 typedef pair<int,int>ii;  9 typedef pair<ll,ii> iii; 10 #define maxn 1001000 11 #define maxm 20100 12 #define se second 13 struct edges{ 14     int to,next;ll dis;int b; 15 }edge[maxm]; 16 int id[1010][1010]; 17 int nxt[maxn],l; 18 inline void addedge(int x,int y,ll z,int b) { 19     edge[++l]=(edges){y,nxt[x],z,b};nxt[x]=l; 20 } 21 #define INF 0x7fffffff 22 #define MAXINF INF*1ll*INF 23 #define fi first 24 #define inf 10000000000000ll 25 int clo=0; 26 int f[maxn],e[maxn]; 27 ll dis[maxn]; 28 bool b[maxn]; 29 int n; 30 inline void dij(int x,int y) { 31     for (int i=1;i<=clo;i++) dis[i]=MAXINF; 32     dis[id[x][y]]=0; 33     static priority_queue<iii,vector<iii>,greater<iii> > q; 34     q.push(iii(0,ii(x,y))); 35     while (!q.empty()){ 36         iii x=q.top();q.pop(); 37         int u=x.se.fi,v=x.se.se; 38         if (b[id[u][v]]) continue; 39         b[id[u][v]]=1; 40         for (int i=nxt[u];i;i=edge[i].next){ 41             ii t; 42             if (edge[i].dis==inf) t=ii(edge[i].to,v+1); 43             else t=ii(edge[i].to,v); 44             if (edge[i].dis==inf&& v==n-1) continue; 45             if (dis[id[t.fi][t.se]]>dis[id[u][v]]+edge[i].dis) { 46                 dis[id[t.fi][t.se]]=dis[id[u][v]]+edge[i].dis; 47                 f[id[t.fi][t.se]]=id[u][v];e[id[t.fi][t.se]]=i; 48                 q.push(iii(dis[id[t.fi][t.se]],t)); 49             } 50         } 51     } 52     return ; 53 } 54 #define M 10010 55 #define N 1010 56 int x[M],y[M]; 57 ll w[M]; 58 int m,s,t; 59 int main(){ 60     ll l; 61     scanf("%d%d%I64d%d%d",&n,&m,&l,&s,&t); 62     s++;t++; 63     for (int i=1;i<=n;i++)  64         for (int j=0;j<n;j++) id[i][j]=++clo; 65     for (int i=1;i<=m;i++) { 66         scanf("%d%d%I64d",x+i,y+i,w+i); 67         x[i]++;y[i]++; 68         if (w[i]==0){  69                 addedge(x[i],y[i],inf,i); 70                 addedge(y[i],x[i],inf,i); 71             } 72         else { 73                 addedge(x[i],y[i],w[i],i); 74                 addedge(y[i],x[i],w[i],i); 75         } 76     } 77     dij(s,0); 78         if (dis[id[t][0]]<l) { 79             printf("NO\n"); 80             return 0; 81         } 82     for (int i=0;i<n;i++) { 83         if (dis[id[t][i]]==MAXINF) continue; 84         if (dis[id[t][i]]%inf>l-i) continue; 85         printf("YES\n"); 86         int u=id[t][i],tmp=l-dis[id[t][i]]%inf; 87         int cnt=0; 88         while (u!=id[s][0]) { 89             if (edge[e[u]].dis==inf) { 90                 cnt++; 91                 if (cnt==i) w[edge[e[u]].b]=tmp; 92                 else { 93                     w[edge[e[u]].b]=1; 94                     tmp--; 95                 } 96             } 97             u=f[u]; 98         } 99         for (int i=1;i<=m;i++) printf("%d %d %I64d\n",x[i]-1,y[i]-1,w[i]?w[i]:inf);100         return 0;101     }102     printf("NO\n");103     return 0;104 }
Complete The Graph

Round #373 :

这一场好像数据出了好多错结果Div 1 unrated了。。。。不过还好Div 2没死然后自己就上Div 1辣(开心),黄学长也因此逃过了掉rate的命运。。。

Div 2 A:Vitya in the Countryside

题意:给定一个月亮阴晴圆缺的序列,求判断接下来月亮是变圆还是变缺

直接判断序列是上升还是下降即可,注意0和15即可

代码:

技术分享
 1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 int n,a[1000]; 7 int main(){ 8     scanf("%d",&n); 9     for (int i=1;i<=n;i++) scanf("%d",a+i);10     if (a[n]==0) {11         printf("UP\n");12         return 0;13     }14     if (a[n]==15) {15         printf("DOWN\n");16         return 0;17     }18     if (n==1) {19         printf("-1\n");20         return 0;21     }22     if (a[n-1]<a[n]) printf("UP\n");23     else printf("DOWN\n");24     return 0;25 }
Vitya in the Countryside

Div 2 B:Anatoly and Cockroaches

题意:给定一串珠子,有两种操作:给一个珠子涂色,交换2个珠子位置,求使这串珠子黑白相间的最小操作

分黑白黑白黑和白黑白黑白考虑咯,然后每次只判断奇位或偶位,看是不是那种颜色,如果不是再考虑要涂色还是交换(有点口胡写的代码也很挫。。。)

代码:

技术分享
 1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 int n,ans,tmp,cnt,sum; 7 char s[100100]; 8 int main(){ 9     scanf("%d",&n);10     scanf("%s",s+1);11     ans=0x7fffffff;12     for (int i=1;i<=n;i++) if (s[i]==b) cnt++;13     tmp=n/2+n%2-cnt;14         sum=0;15         for (int i=1;i<=n;i++) 16             if (i%2==1&&s[i]==r) sum++ ;17         if (tmp>=0){18         ans=min(ans,max(tmp,sum));19     }20     tmp-=n%2;21     if (tmp>=0) {22     ans=min(ans,max(tmp,n-cnt-sum));23     }24     cnt=n-cnt;25     tmp=n/2-cnt+n%2;26     sum=0;27     for (int i=1;i<=n;i++) 28         if (i%2==1&&s[i]==b) sum++;29     if (tmp>=0) {30     ans=min(ans,max(tmp,sum));31     }32     tmp-=n%2;33     if (tmp>=0) { 34     ans=min(ans,max(tmp,n-cnt-sum));35     }36 //    printf("%d %d %d %d\n",tmp,sum,cnt,ans);37     printf("%d\n",ans);38     return 0;39 }
Anatoly and Cockraches

Div 2 C and Div 1 A Efim and Strange Grade

题意:给定一个浮点数,有n次四舍五入的机会,求获得最大的数大小

从高位到低位找到第一个大于5的数位进位即可,主要注意输出格式和进位问题就没了

代码:

技术分享
 1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<iostream> 5 #include<queue> 6 using namespace std; 7 typedef pair<int,int> ii; 8 #define fi first 9 #define se second10 priority_queue<int,vector<int>,greater<int> > q;11 int n,m,flag=0,cnt;12 char s[200010];13 int main(){14     scanf("%d%d",&n,&m);15     scanf("%s",s+1);16     for (int i=1;i<=n;i++) {17         if (s[i]==.) {cnt=i;flag=1;continue;}18         if (flag==1 && s[i]>4) q.push(i);19     }20     if (!flag) {printf("%s\n",s+1);return 0;}21     flag=1;22     int lst=n+1;23     for (int i=1;i<=m;i++) {24         if (q.empty()) break;25         int u=q.top();q.pop();26         if (u>lst ) break;27         lst=u;28         if (u==cnt+1) {29             int t=u-2;30             while (s[t]==9) s[t]=0,t--;31             if (t==0) {flag=0;s[t]=1;}32             else s[t]++;33         }34         else {35             s[u-1]++;36             if (s[u-1]>4) q.push(u-1);37         }38         s[u]=0;39     }40     int n=lst-1;41     for (;s[n]==0;n--); 42     s[n+1]=0;43     if (s[n]==.) s[n]=0;44     printf("%s\n",s+flag);45     return 0;46 }
Efim and Strange Grade

Div 2 D and Div 1 B

虽然是一道错题不过解法还是挺机智的

题意:有N个复印机,每个复印机复印文件要ti秒,现在有m个任务,每个任务要求需要x个副本,求复印所需要的最小时间

先把  每个复印机投入工作的时间计算出来记为si,然后二分时间T,那么时间T内的副本数就为$\sum_{i=1}^n \lfloor \frac{T-si}{ti} \rfloor$但因为复印机数太多所以还是过不了,考虑到$1<=ti<=1000$ 那么就把复印时间相同的复印机放在一起处理

Div 2 E and Div 1 C Sasha and Array

题意:给定一个序列,支持区间加法和区间求其斐波那契数之和

线段树+矩阵乘法裸题,注意点优化就行了,例如lazy直接存斐波那契数的矩阵什么的就没问题了

代码:

技术分享
  1 #include<queue>  2 #include<cmath>  3 #include<cstdio>  4 #include<cstring>  5 #include<cstdlib>  6 #include<iostream>  7 #include<algorithm>  8 typedef  long long ll;  9 #define inf 0x7fffffff 10 #define mod 1000000007 11 using namespace std; 12 int n,m; 13 struct M{ 14     ll v[3][3]; 15     M(){ 16         memset(v,0,sizeof(v)); 17     } 18     friend M operator*(M a,M b){ 19         M c; 20         for(int i=1;i<=2;i++) 21             for(int j=1;j<=2;j++)        22                 for(int k=1;k<=2;k++) 23                     c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j]%mod)%mod; 24         return c; 25     } 26     friend M operator+(M a,M b){ 27         for(int i=1;i<=2;i++) 28             for(int j=1;j<=2;j++) 29                 (a.v[i][j]+=b.v[i][j])%=mod; 30         return a; 31     } 32     friend M operator^(M a,int b){ 33         M ans; 34         for(int i=1;i<=2;i++) 35             ans.v[i][i]=1; 36         for(int i=b;i;i>>=1,a=a*a) 37             if(i&1)ans=ans*a; 38         return ans; 39     } 40 }T,U,V; 41 inline void init() { 42     memset(T.v,0,sizeof(T.v)); 43     memset(U.v,0,sizeof(T.v)); 44     memset(V.v,0,sizeof(T.v)); 45     T.v[1][1]=T.v[1][2]=T.v[2][1]=1; 46     U.v[1][1]=V.v[1][1]=V.v[2][2]=1; 47 } 48 #define maxn 100100 49 struct node{ 50     int l,r;M m,lz; 51 }t[maxn*4]; 52 #define lc (x<<1) 53 #define rc (lc+1) 54 #define mid ((l+r)>>1) 55 int a[maxn]; 56 inline void update(int x) { 57     t[x].m=t[lc].m+t[rc].m; 58 } 59 inline void pb(int x) { 60     t[lc].m=t[x].lz*t[lc].m; 61     t[lc].lz=t[x].lz*t[lc].lz; 62     t[rc].m=t[x].lz*t[rc].m; 63     t[rc].lz=t[x].lz*t[rc].lz; 64     t[x].lz=V; 65 } 66 void build(int x,int l,int r) { 67     t[x].l=l,t[x].r=r;t[x].lz=V; 68     if (l==r) { 69         t[x].m=(T^(a[l]-1))*U; 70         return ; 71     } 72     build(lc,l,mid);build(rc,mid+1,r); 73     update(x); 74     return ; 75 } 76 void add(int x,int le,int ri,M y) { 77     int l=t[x].l,r=t[x].r; 78     if (l>ri||r<le) return ; 79     if (le<=l&&r<=ri) { 80         t[x].lz=t[x].lz*y; 81         t[x].m=y*t[x].m; 82         return ; 83     } 84     pb(x); 85     add(lc,le,ri,y);add(rc,le,ri,y); 86     update(x); 87     return ; 88 } 89 ll sum(int x,int le,int ri) { 90     int l=t[x].l,r=t[x].r; 91     if (l>ri||r<le) return 0; 92     if (le<=l&&r<=ri) return t[x].m.v[1][1]; 93     pb(x); 94     return (sum(lc,le,ri)+sum(rc,le,ri))%mod; 95 } 96 int main(){ 97     init(); 98     scanf("%d%d",&n,&m); 99     for (int i=1;i<=n;i++) scanf("%d",a+i);100     build(1,1,n);101     while (m--) {102         int opt,l,r,x;103         scanf("%d",&opt);104         switch (opt) {105             case 1: 106                 scanf("%d%d%d",&l,&r,&x);107                 add(1,l,r,T^x);108                 break;109             case 2:110                 scanf("%d%d",&l,&r);111                 printf("%I64d\n",sum(1,l,r));112                 break;113         }114     }115     return 0;116 }
Sasha and Array

 

Codeforces Round #372 +#373 部分题解