Codeforces Round #372 +#373 部分题解

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

Round #372 :

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

直接模拟没有什么好说的

代码：

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int main(){

     int n,c;

     scanf("%d%d",&n,&c);

     int last=,cnt=;

     for (int i=;i<=n;i++) {

         int x;

         scanf("%d",&x);

         if (x-last>c) cnt=;

         last=x;cnt++;

     }

     printf("%d\n",cnt);

     return ;

 }

Crazy Computer

Div 2 B：Complete the Word

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

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

代码：

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 char s[];

 int a[],n;

 int cnt=;

 int main(){

     scanf("%s",s+);

     int n=strlen(s+);

     int l=;

     int cnt=;

     for (int i=;i<=n;i++){

         if (s[i]=='?') {

             cnt++;

         }else {

             int t=s[i]-'A'+;

             if (a[t]==) {

                 while (s[i]!=s[l]) {

                     if (s[l]=='?') {

                         cnt--;

                     }else a[s[l]-'A'+]--;

                     l++;

                 }

                 if (s[l]=='?') cnt--;

                 else a[s[l]-'A'+]--;

                 l++;

             }

             a[t]++;

         }

         if (i-l+==) {

             for (int j=;j<l;j++) printf("%c",s[j]=='?'?'A':s[j]);

             for (int j=l;j<=i;j++) {

                 if (s[j]!='?') printf("%c",s[j]);

                 else {

                     for (int k=;k<=;k++) {

                         if (a[k]) continue;

                         printf("%c",k+'A'-);

                         a[k]++;

                         break;

                     }

                 }

             }

             for (int j=i+;j<=n;j++) printf("%c",s[j]=='?'?'A':s[j]);

             return ;

         }

     }

     printf("-1\n");

     return ;

 }

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)$ 即可

代码：

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 ll n,x;

 int main(){

 cin>>n;

 x=;

 for (ll i=;i<=n;i++) {

     ll ans=(i+)*(i+)*i-x/i;

     cout<<ans<<endl;

     x=i*(i+);

 }

 }

Plus and Square Root

Div 2 D and Div 1 B：Complete The Graph

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

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

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

代码：

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int>ii;

 typedef pair<ll,ii> iii;

 #define maxn 1001000

 #define maxm 20100

 #define se second

 struct edges{

     int to,next;ll dis;int b;

 }edge[maxm];

 int id[][];

 int nxt[maxn],l;

 inline void addedge(int x,int y,ll z,int b) {

     edge[++l]=(edges){y,nxt[x],z,b};nxt[x]=l;

 }

 #define INF 0x7fffffff

 #define MAXINF INF*1ll*INF

 #define fi first

 #define inf 10000000000000ll

 int clo=;

 int f[maxn],e[maxn];

 ll dis[maxn];

 bool b[maxn];

 int n;

 inline void dij(int x,int y) {

     for (int i=;i<=clo;i++) dis[i]=MAXINF;

     dis[id[x][y]]=;

     static priority_queue<iii,vector<iii>,greater<iii> > q;

     q.push(iii(,ii(x,y)));

     while (!q.empty()){

         iii x=q.top();q.pop();

         int u=x.se.fi,v=x.se.se;

         if (b[id[u][v]]) continue;

         b[id[u][v]]=;

         for (int i=nxt[u];i;i=edge[i].next){

             ii t;

             if (edge[i].dis==inf) t=ii(edge[i].to,v+);

             else t=ii(edge[i].to,v);

             if (edge[i].dis==inf&& v==n-) continue;

             if (dis[id[t.fi][t.se]]>dis[id[u][v]]+edge[i].dis) {

                 dis[id[t.fi][t.se]]=dis[id[u][v]]+edge[i].dis;

                 f[id[t.fi][t.se]]=id[u][v];e[id[t.fi][t.se]]=i;

                 q.push(iii(dis[id[t.fi][t.se]],t));

             }

         }

     }

     return ;

 }

 #define M 10010

 #define N 1010

 int x[M],y[M];

 ll w[M];

 int m,s,t;

 int main(){

     ll l;

     scanf("%d%d%I64d%d%d",&n,&m,&l,&s,&t);

     s++;t++;

     for (int i=;i<=n;i++)

         for (int j=;j<n;j++) id[i][j]=++clo;

     for (int i=;i<=m;i++) {

         scanf("%d%d%I64d",x+i,y+i,w+i);

         x[i]++;y[i]++;

         if (w[i]==){

                 addedge(x[i],y[i],inf,i);

                 addedge(y[i],x[i],inf,i);

             }

         else {

                 addedge(x[i],y[i],w[i],i);

                 addedge(y[i],x[i],w[i],i);

         }

     }

     dij(s,);

         if (dis[id[t][]]<l) {

             printf("NO\n");

             return ;

         }

     for (int i=;i<n;i++) {

         if (dis[id[t][i]]==MAXINF) continue;

         if (dis[id[t][i]]%inf>l-i) continue;

         printf("YES\n");

         int u=id[t][i],tmp=l-dis[id[t][i]]%inf;

         int cnt=;

         while (u!=id[s][]) {

             if (edge[e[u]].dis==inf) {

                 cnt++;

                 if (cnt==i) w[edge[e[u]].b]=tmp;

                 else {

                     w[edge[e[u]].b]=;

                     tmp--;

                 }

             }

             u=f[u];

         }

         for (int i=;i<=m;i++) printf("%d %d %I64d\n",x[i]-,y[i]-,w[i]?w[i]:inf);

         return ;

     }

     printf("NO\n");

     return ;

 }

Complete The Graph

Round #373 ：

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

Div 2 A：Vitya in the Countryside

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

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

代码:

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int n,a[];

 int main(){

     scanf("%d",&n);

     for (int i=;i<=n;i++) scanf("%d",a+i);

     if (a[n]==) {

         printf("UP\n");

         return ;

     }

     if (a[n]==) {

         printf("DOWN\n");

         return ;

     }

     if (n==) {

         printf("-1\n");

         return ;

     }

     if (a[n-]<a[n]) printf("UP\n");

     else printf("DOWN\n");

     return ;

 }

Vitya in the Countryside

Div 2 B:Anatoly and Cockroaches

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

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

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 using namespace std;

 int n,ans,tmp,cnt,sum;

 char s[];

 int main(){

     scanf("%d",&n);

     scanf("%s",s+);

     ans=0x7fffffff;

     for (int i=;i<=n;i++) if (s[i]=='b') cnt++;

     tmp=n/+n%-cnt;

         sum=;

         for (int i=;i<=n;i++)

             if (i%==&&s[i]=='r') sum++ ;

         if (tmp>=){

         ans=min(ans,max(tmp,sum));

     }

     tmp-=n%;

     if (tmp>=) {

     ans=min(ans,max(tmp,n-cnt-sum));

     }

     cnt=n-cnt;

     tmp=n/-cnt+n%;

     sum=;

     for (int i=;i<=n;i++)

         if (i%==&&s[i]=='b') sum++;

     if (tmp>=) {

     ans=min(ans,max(tmp,sum));

     }

     tmp-=n%;

     if (tmp>=) {

     ans=min(ans,max(tmp,n-cnt-sum));

     }

 //    printf("%d %d %d %d\n",tmp,sum,cnt,ans);

     printf("%d\n",ans);

     return ;

 }

Anatoly and Cockraches

Div 2 C and Div 1 A Efim and Strange Grade

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

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

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<queue>

 using namespace std;

 typedef pair<int,int> ii;

 #define fi first

 #define se second

 priority_queue<int,vector<int>,greater<int> > q;

 int n,m,flag=,cnt;

 char s[];

 int main(){

     scanf("%d%d",&n,&m);

     scanf("%s",s+);

     for (int i=;i<=n;i++) {

         if (s[i]=='.') {cnt=i;flag=;continue;}

         if (flag== && s[i]>'') q.push(i);

     }

     if (!flag) {printf("%s\n",s+);return ;}

     flag=;

     int lst=n+;

     for (int i=;i<=m;i++) {

         if (q.empty()) break;

         int u=q.top();q.pop();

         if (u>lst ) break;

         lst=u;

         if (u==cnt+) {

             int t=u-;

             while (s[t]=='') s[t]='',t--;

             if (t==) {flag=;s[t]='';}

             else s[t]++;

         }

         else {

             s[u-]++;

             if (s[u-]>'') q.push(u-);

         }

         s[u]=;

     }

     int n=lst-;

     for (;s[n]=='';n--);

     s[n+]=;

     if (s[n]=='.') s[n]=;

     printf("%s\n",s+flag);

     return ;

 }

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直接存斐波那契数的矩阵什么的就没问题了

代码：

 #include<queue>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 typedef  long long ll;

 #define inf 0x7fffffff

 #define mod 1000000007

 using namespace std;

 int n,m;

 struct M{

     ll v[][];

     M(){

         memset(v,,sizeof(v));

     }

     friend M operator*(M a,M b){

         M c;

         for(int i=;i<=;i++)

             for(int j=;j<=;j++)

                 for(int k=;k<=;k++)

                     c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j]%mod)%mod;

         return c;

     }

     friend M operator+(M a,M b){

         for(int i=;i<=;i++)

             for(int j=;j<=;j++)

                 (a.v[i][j]+=b.v[i][j])%=mod;

         return a;

     }

     friend M operator^(M a,int b){

         M ans;

         for(int i=;i<=;i++)

             ans.v[i][i]=;

         for(int i=b;i;i>>=,a=a*a)

             if(i&)ans=ans*a;

         return ans;

     }

 }T,U,V;

 inline void init() {

     memset(T.v,,sizeof(T.v));

     memset(U.v,,sizeof(T.v));

     memset(V.v,,sizeof(T.v));

     T.v[][]=T.v[][]=T.v[][]=;

     U.v[][]=V.v[][]=V.v[][]=;

 }

 #define maxn 100100

 struct node{

     int l,r;M m,lz;

 }t[maxn*];

 #define lc (x<<1)

 #define rc (lc+1)

 #define mid ((l+r)>>1)

 int a[maxn];

 inline void update(int x) {

     t[x].m=t[lc].m+t[rc].m;

 }

 inline void pb(int x) {

     t[lc].m=t[x].lz*t[lc].m;

     t[lc].lz=t[x].lz*t[lc].lz;

     t[rc].m=t[x].lz*t[rc].m;

     t[rc].lz=t[x].lz*t[rc].lz;

     t[x].lz=V;

 }

 void build(int x,int l,int r) {

     t[x].l=l,t[x].r=r;t[x].lz=V;

     if (l==r) {

         t[x].m=(T^(a[l]-))*U;

         return ;

     }

     build(lc,l,mid);build(rc,mid+,r);

     update(x);

     return ;

 }

 void add(int x,int le,int ri,M y) {

     int l=t[x].l,r=t[x].r;

     if (l>ri||r<le) return ;

     if (le<=l&&r<=ri) {

         t[x].lz=t[x].lz*y;

         t[x].m=y*t[x].m;

         return ;

     }

     pb(x);

     add(lc,le,ri,y);add(rc,le,ri,y);

     update(x);

     return ;

 }

 ll sum(int x,int le,int ri) {

     int l=t[x].l,r=t[x].r;

     if (l>ri||r<le) return ;

     if (le<=l&&r<=ri) return t[x].m.v[][];

     pb(x);

     return (sum(lc,le,ri)+sum(rc,le,ri))%mod;

 }

 int main(){

     init();

     scanf("%d%d",&n,&m);

     for (int i=;i<=n;i++) scanf("%d",a+i);

     build(,,n);

     while (m--) {

         int opt,l,r,x;

         scanf("%d",&opt);

         switch (opt) {

             case :

                 scanf("%d%d%d",&l,&r,&x);

                 add(,l,r,T^x);

                 break;

             case :

                 scanf("%d%d",&l,&r);

                 printf("%I64d\n",sum(,l,r));

                 break;

         }

     }

     return ;

 }

Sasha and Array

巴特西

Codeforces Round #372 +#373 部分题解

最新文章

热门文章