蒟蒻只能打div 2

?

A題水，10和個位數的使用互不影響，所以直接在模10意義下做

1 #include<bits/stdc++.h> 2 using namespace std; 3 int k,r; 4 int main(){ 5 scanf("%d%d",&k,&r); 6 k=k%10; 7 for(int i=1;i<=100;i++){ 8 if(k*i%10==0||k*i%10==r) { 9 printf("%d\n",i);break; 10 } 11 } 12 return 0; 13 } View Code

?

B從左往右遞推即可，先決定左邊，然后向右走一天。

1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,k,r,x[505],y[505],ans; 4 int main(){ 5 scanf("%d%d",&n,&k); 6 for(int i=1;i<=n;i++) scanf("%d",&x[i]); 7 x[0]=k;x[n+1]=k; 8 for(int i=0;i<=n;i++){ 9 if(x[i]+x[i+1]<k) ans+=k-x[i]-x[i+1],x[i+1]=k-x[i]; 10 }printf("%d\n",ans); 11 for(int i=1;i<n;i++) printf("%d ",x[i]); 12 printf("%d\n",x[n]); 13 return 0; 14 } View Code

?

C題寫了個討論

題目大意就是，給你一個人在連續n天里吃了多少頓早餐，午餐，晚餐，問你他最少有多少頓沒吃。他來的那天和走的那天可以在任意一餐后（或前）來。

例：

1 2 1

answer:0

在第一天午餐前來，吃午餐和晚餐，第二天午餐后走，吃午餐和早餐。

4 2 4

answer:1

在第一天晚餐前來，第二或第三或第四天有一天沒吃午餐，第五天早餐后走。

看哪個最大，討論即可

1 #include<bits/stdc++.h> 2 using namespace std; 3 long long b[4]; 4 int main(){ 5 scanf("%I64d%I64d%I64d",&b[1],&b[2],&b[3]); 6 int num=0,q=0;b[0]=-1; 7 for(int i=1;i<=3;i++) if(b[i]>b[num]) num=i; 8 for(int i=1;i<=3;i++) if(b[i]==b[num]) q++; 9 if(q==3) { 10 printf("0\n");return 0; 11 } 12 if(q==2){ 13 for(int i=1;i<=3;i++) if(b[i]!=b[num]) q=i; 14 printf("%I64d\n",b[num]-b[q]-1); 15 return 0; 16 } 17 b[num]--;int qum=0; 18 printf("%I64d\n",3*b[num]-b[1]-b[2]-b[3]); 19 return 0; 20 } View Code

?

D題

題意

有n天，m科考試，給出每一天可以過哪一科，以及每科需要多少天復習，求最少要多少天考完，或者不可能。

D題想不到怎么做，就去看代碼，看到一個神解法，完全沒有理論依據（在我看來），隨便一組數據就能hack掉（如6 2 2 2 2 2 2 2 1 2），可惜不知道cf怎么比賽后hack。

1 #include<bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int n,m; 6 cin>>n>>m; 7 int arr[n+1]; 8 for(int i=1;i<=n;i++)cin>>arr[i]; 9 int sum=m,x; 10 for(int i=0;i<m;i++){cin>>x; sum+=x;} 11 12 for(int i=sum;i<=n;i++)if(arr[i]){cout<<i; return 0;} 13 cout<<-1; 14 } 神解法

正解是二分加貪心，從后往前。

可以知道，對于單獨一個科目，晚幾天考試不會比先考差。

于是二分答案的天數，從后往前的時候每遇到一個沒有考過的科目，就把它考了，然后把需要復習的時間加上當前考試需復習的時間。

如果該天不考試，需復習的時間就減1，但注意不能減到0以下，不然會出現在考完后復習的情況。

代碼里寫的是反著的，cnt是可以復習的天數，不能為正。

1 #include<bits/stdc++.h> 2 #define maxn 100005 3 using namespace std; 4 int n,m,tot,x[maxn],cnt,ti[maxn]; 5 bool y[maxn]; 6 bool test(int r){ 7 cnt=0;tot=m;y[0]=1; 8 for(int i=r;i>=1;i--){ 9 if(!y[x[i]]) { 10 if(cnt>0) cnt=0; 11 y[x[i]]=1;tot--;cnt-=ti[x[i]]; 12 } 13 else cnt++; 14 } 15 if(tot>0 || cnt<0) return 0; 16 return 1; 17 } 18 int main(){ 19 scanf("%d%d",&n,&m); 20 for(int i=1;i<=n;i++){ 21 scanf("%d",&x[i]); 22 } 23 for(int i=1;i<=m;i++){ 24 scanf("%d",&ti[i]); 25 } 26 int l=1,r=n,mid; 27 while(l<r){ 28 mid=l+r>>1; 29 if(test(mid)) r=mid; 30 else l=mid+1; 31 memset(y,0,sizeof(y)); 32 } 33 if(l==n) if(!test(l)){ 34 printf("-1\n");return 0; 35 } 36 printf("%d\n",l); 37 return 0; 38 } View Code

?

E題

題意：有n個電腦，m個插座，每個電腦和每個插座都有一個power值，當且僅當插座和電腦的power值完全相同時，電腦和插座能夠配對，一個插座只能對應一個電腦。每個插座可以加上一個轉換裝置，使它的power值變為原來的一半（向上取整，）。求配對的電腦數最大的情況下，可行的最少裝置使用數，每個插座使用的裝置數，以及當前的電腦和插座的配對情況。

一看以為是網絡流裸題，看了看n<=200000復雜度不對，接著發現一個顯然的貪心，一個插座如果不使用裝置能和電腦配對，那它們配對一定不會是情況變差，然后就想到set判重，先把一開始就配對的去掉。然后就想到一個插座最多使用log10^9個裝置，且最多有log10^9 個不同的值，之后如果再使用裝置，它的power值會一直停留在1。然后我想既然能用set，為什么我不寫個排序加二分呢？然后我發現我先前的貪心依然使用，即在已經嘗試完所有每個插座使用小于k個裝置的情況后，如果一個插座使用k個裝置能和一個電腦配對，那它們配對一定不會使情況變差。于是從小到大枚舉裝置的使用個數，更新未使用插座的power值，二分查找看是否有未配對且power相同的電腦，進行配對。注意要先預處理把power相同的電腦放在一起，不然二分很不好寫。

1 #include<bits/stdc++.h> 2 #define maxn 200005 3 using namespace std; 4 pair<int,int> h[maxn]; 5 struct ed{int next,pos;}e[maxn]; 6 int n,m,y[maxn],socka[maxn],head[maxn],qet,belog[maxn],tot,cnt,pre,x[maxn]; 7 int main(){ 8 scanf("%d%d",&n,&m); 9 int l,r,mid; 10 for(int i=1;i<=n;i++) scanf("%d",&x[i]),h[i].first=x[i],h[i].second=i; 11 sort(x+1,x+n+1);sort(h+1,h+n+1);pre=0; 12 for(int i=1;i<=n;i++){ 13 if(x[i]==x[pre]) { 14 qet++;e[qet].next=head[pre];head[pre]=qet;e[qet].pos=h[i].second;; 15 } 16 else{ 17 pre++;qet++;e[qet].pos=h[i].second;x[pre]=x[i];e[qet].next=head[pre];head[pre]=qet; 18 } 19 } 20 for(int i=1;i<=m;i++) scanf("%d",&y[i]); 21 for(int i=1;i<=m;i++){ 22 l=1;r=pre; 23 while(l<r){ 24 mid=l+r>>1; 25 if(x[mid]>=y[i]) r=mid; 26 if(x[mid]<y[i]) l=mid+1; 27 } 28 if(x[l]==y[i]){ 29 if(head[l]){ 30 belog[e[head[l]].pos]=i; 31 socka[i]=1;tot++;head[l]=e[head[l]].next; 32 } 33 } 34 } 35 for(int k=2;k<=32;k++) 36 for(int i=1;i<=m;i++){ 37 if(socka[i]) continue; 38 if(y[i]%2) y[i]=y[i]/2+1; 39 else y[i]/=2; 40 l=1;r=pre; 41 while(l<r){ 42 mid=l+r>>1; 43 if(x[mid]>=y[i]) r=mid; 44 if(x[mid]<y[i]) l=mid+1; 45 } 46 if(x[l]==y[i]){ 47 if(head[l]){ 48 belog[e[head[l]].pos]=i; 49 socka[i]=k;tot++;cnt+=k-1;head[l]=e[head[l]].next; 50 } 51 } 52 } 53 printf("%d %d\n",tot,cnt); 54 for(int i=1;i<m;i++){ 55 if(socka[i]) socka[i]--; 56 printf("%d ",socka[i]); 57 }if(socka[m]) socka[m]--;printf("%d\n",socka[m]); 58 for(int i=1;i<n;i++) printf("%d ",belog[i]); 59 printf("%d\n",belog[n]); 60 return 0; 61 } View Code

?

F題：讀懂題意后一眼秒。

題目：給一個n個點m條無向邊的無重邊自環的連通圖，讓你把所有的邊定向，使得從每個點出發能夠到達的點數中，最小的那個盡量大。

一眼題：

先看一條鏈，無論怎么連邊，ans都是1.

于是想到找環，若有兩個環，不能相加，而是選最大的那個。

于是題目變成找最大環。

我用了tarjan，維護了一下環的大小。

只是要求輸出每條邊的定向很麻煩。

我一開始是想先把最大環上的定向，其他邊通過dfs連一連就行，然后發現其他的環與不在環上的點的邊會重復輸出。

然后我改了一會就棄療了

去看了一位紅名大佬quality的代碼，發現他跑了兩遍tarjan

第二遍是給邊定向用的。

為什么是對的呢？我也不知道，好像從最大環上dfs一發就可以了，完全不需要用tarjan。

于是我學著dalao的樣子改了改，交了幾遍過了。

看來亂搞能力還是太弱。。。

1 #include<bits/stdc++.h> 2 #define maxn 400005 3 using namespace std; 4 int n,m,head[maxn],cnt=0,df,dfn[maxn],compcnt,low[maxn],comphead[maxn],que[maxn],qcnt,compsize[maxn]; 5 bool inque[maxn],vis[maxn],incomp[maxn]; 6 int ba[maxn],bq[maxn],res[maxn],q,oow=(1<<30)-2; 7 struct edges{int next,to,fr;}e[4*maxn]; 8 void tarjan(int k,int f){ 9 que[++qcnt]=k;inque[k]=1; 10 dfn[k]=++df; 11 low[k]=min(low[k],dfn[k]); 12 for(int i=head[k];i;i=e[i].next){ 13 if(e[i].to==f) continue;if(i%2==0) q=i-1;else q=i; 14 q=q>>1;q++; 15 if(res[q]<0) res[q]=~i&1; 16 if(!dfn[e[i].to]) { 17 tarjan(e[i].to,k); 18 low[k]=min(low[k],low[e[i].to]); 19 } 20 else{ 21 if(inque[e[i].to]) low[k]=min(low[k],dfn[e[i].to]); 22 } 23 } 24 if(dfn[k]==low[k]){ 25 compcnt++; 26 while(que[qcnt]!=k) 27 { 28 inque[e[cnt].to]=0; 29 cnt++; 30 e[cnt].next=comphead[compcnt]; 31 comphead[compcnt]=cnt; 32 e[cnt].to=que[qcnt--]; 33 compsize[compcnt]++; 34 } 35 inque[e[cnt].to]=0; 36 cnt++; 37 e[cnt].next=comphead[compcnt]; 38 comphead[compcnt]=cnt; 39 e[cnt].to=que[qcnt--]; 40 compsize[compcnt]++; 41 } 42 } 43 int main(){ 44 scanf("%d%d",&n,&m);int a,b; 45 for(int i=1;i<=m;i++){ 46 scanf("%d%d",&a,&b); 47 e[++cnt].to=b;e[cnt].next=head[a];head[a]=cnt;e[cnt].fr=a; 48 e[++cnt].to=a;e[cnt].next=head[b];head[b]=cnt;e[cnt].fr=b; 49 } 50 for(int i=1;i<=n;i++) low[i]=n+1; 51 tarjan(1,0); 52 int maxcomp=0,maxcompsize=0; 53 for(int i=1;i<=compcnt;i++){ 54 if(compsize[i]>maxcompsize) { 55 maxcompsize=compsize[i]; 56 maxcomp=i; 57 } 58 } 59 printf("%d\n",maxcompsize); 60 memset(dfn,0,sizeof(dfn)); 61 memset(inque,0,sizeof(inque)); 62 memset(res,-1,sizeof(res));df=0;qcnt=0;compcnt=0; 63 tarjan(e[comphead[maxcomp]].to,0); 64 for(int i=1;i<=m;i++){ 65 if(res[i]) printf("%d %d\n",e[i*2-1].fr,e[i*2-1].to); 66 else printf("%d %d\n",e[i*2-1].to,e[i*2-1].fr); 67 } 68 return 0; 69 } View Code

?

?

轉載于:https://www.cnblogs.com/awipppp/p/5979925.html

總結

以上是生活随笔為你收集整理的Codeforces Round #377 (Div. 2) 732A B C D E F的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。