A题：一个三角形，一开始在C点，给边长a,b,c问上面走n-1次走多少步。
？？？为什么会写错？？？
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> //#include<assert.h> #include<math.h> //#include<iostream> using namespace std; int a,b,c,n; int main() { scanf("%d%d%d%d",&n,&a,&b,&c); int ans=0; if (n==1) printf("0 "); else if (a<=b && a<=c) printf("%d ",a*(n-1));//不要少了等于号！！！！ else if (b<=c && b<=a) printf("%d ",b*(n-1));//不要少了等于号！！！！ else printf("%d ",min(a,b)+c*(n-2)); return 0; }
B题：膜m意义下同个值超过K个即可。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> //#include<assert.h> #include<math.h> //#include<iostream> using namespace std; int n,K,m; #define maxn 100011 int a[maxn],cnt[maxn]; int main() { scanf("%d%d%d",&n,&K,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i]),cnt[a[i]%m]++; int ans=-1; for (int i=0;i<m;i++) if (cnt[i]>=K) ans=i; if (ans<0) printf("No "); else { puts("Yes"); int cc=0; for (int i=1;i<=n;i++) { if (a[i]%m==ans) cc++,printf("%d ",a[i]); if (cc==K) break; } } return 0; }
C题：设答案x，n-x>=9*9，检测n前面若干个数即可。
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<algorithm> 5 //#include<assert.h> 6 #include<math.h> 7 //#include<iostream> 8 using namespace std; 9 10 int n,anss[10000],ans; 11 int main(){ 12 scanf("%d",&n); 13 int m=max(1,n-100); 14 int num,x; 15 for(int i=m;i<=n;i++){ 16 x=i;num=i; 17 while(x){num+=x%10;x/=10;} 18 if(num==n)anss[++ans]=i; 19 } 20 printf("%d ",ans); 21 for(int i=1;i<=ans;i++)printf("%d ",anss[i]); 22 return 0; 23 }
D题：（读题读了半天。。）最后连续的X号不算，其他X都使答案+1，所以每次把最后的X号连在一起不算即可。
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<algorithm> 5 //#include<assert.h> 6 #include<math.h> 7 //#include<iostream> 8 using namespace std; 9 10 #define maxn 300011 11 int n,a[maxn],b[maxn]; 12 int main(){ 13 scanf("%d",&n); 14 int tail=n;printf("1 "); 15 int num=0; 16 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 17 for(int i=1;i<=n;i++){ 18 b[a[i]]++; 19 num++; 20 while(b[tail]&&tail>0)tail--,num--; 21 printf("%d ",num+1); 22 } 23 return 0; 24 }
E题：经典2-SAT问题！
话说CF造一个1连到1e5的数据卡我dfs是不是很可恶啊。。。。。。以后枚举都从m到1吧。。
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<algorithm> 5 //#include<vector> 6 //#include<assert.h> 7 #include<math.h> 8 #include<queue> 9 //#include<iostream> 10 using namespace std; 11 12 int n,m; 13 #define maxn 300011 14 struct Edge{int to,next;}edge[maxn<<1];int first[maxn],le=2; 15 void in(int x,int y) {Edge &e=edge[le];e.to=y;e.next=first[x];first[x]=le++;} 16 void in1(int x,int y) 17 { 18 in(x,y); 19 in(y+m,x+m); 20 } 21 void in2(int x,int y) 22 { 23 in(x,x+m); 24 in(y+m,y); 25 } 26 int vis[maxn<<1],sta[maxn<<1],top; 27 bool dfs(int x) 28 { 29 // cout<<x<<endl; 30 if ((x>m && vis[x-m]) || (x<=m && vis[x+m])) return 0; 31 if (vis[x]) return 1; 32 vis[x]=1;sta[++top]=x; 33 for (int i=first[x];i;i=edge[i].next) 34 { 35 const Edge &e=edge[i]; 36 if (!dfs(e.to)) return 0; 37 } 38 return 1; 39 } 40 bool twosat() 41 { 42 top=0; 43 for (int i=m;i>=1;i--) 44 if (!vis[i] && !vis[i+m]) 45 { 46 top=0; 47 if (!dfs(i)) 48 { 49 while (top) vis[sta[top--]]=0; 50 if (!dfs(i+m)) return 0; 51 } 52 } 53 return 1; 54 } 55 vector<int> v[maxn]; 56 int main() 57 { 58 // freopen("in2.txt","r",stdin); 59 scanf("%d%d",&n,&m); 60 int l,x; 61 for (int i=1;i<=n;i++) 62 { 63 scanf("%d",&l); 64 for (int j=1;j<=l;j++) scanf("%d",&x),v[i].push_back(x); 65 } 66 bool flag=0; 67 for (int i=1;i<n;i++) 68 { 69 bool equal=1; 70 for (int j=0;j<min(v[i+1].size(),v[i].size());j++) 71 { 72 if (v[i][j]<v[i+1][j]) 73 { 74 in1(v[i][j],v[i+1][j]); 75 equal=0; 76 break; 77 } 78 else if (v[i][j]>v[i+1][j]) 79 { 80 in2(v[i][j],v[i+1][j]); 81 equal=0; 82 break; 83 } 84 } 85 if (equal && v[i].size()>v[i+1].size()) {flag=1;break;} 86 } 87 if (flag) puts("No"); 88 else if (twosat()) 89 { 90 // cout<<":)"; 91 puts("Yes"); 92 int cnt=0; 93 for (int i=1;i<=m;i++) if (vis[i+m]) cnt++; 94 printf("%d ",cnt); 95 for (int i=1;i<=m;i++) if (vis[i+m]) printf("%d ",i); 96 } 97 else puts("No"); 98 return 0; 99 }
F题：找每个数作为山峰的区间统计答案，枚举每个山作山峰，用四个东西算出它对答案的贡献：左边的第一个比他大的数，右边第一个比他大的数，以及在上面两个数的范围内，离他最近的的和枚举的这个山峰取或之后会变大的数，左右两边各一个，然后乘一下即可。
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<algorithm> 5 //#include<assert.h> 6 #include<math.h> 7 #include<iostream> 8 using namespace std; 9 10 int n; 11 #define maxn 200011 12 int a[maxn],lmax[maxn],rmax[maxn],lch[maxn],rch[maxn],sta[maxn],top; 13 int hus[33][maxn],hut[33]; 14 #define LL long long 15 int main() 16 { 17 scanf("%d",&n); 18 for (int i=1;i<=n;i++) scanf("%d",&a[i]); 19 top=0; 20 for (int i=1;i<=n;i++) 21 { 22 while (top && a[sta[top]]<=a[i]) top--; 23 if (!top) lmax[i]=1; 24 else lmax[i]=sta[top]+1; 25 sta[++top]=i; 26 } 27 top=0; 28 for (int i=n;i>=1;i--) 29 { 30 while (top && a[sta[top]]<a[i]) top--; 31 if (!top) rmax[i]=n; 32 else rmax[i]=sta[top]-1; 33 sta[++top]=i; 34 } 35 memset(hut,0,sizeof(hut)); 36 for (int i=1;i<=n;i++) 37 { 38 lch[i]=0; 39 for (int j=0;j<=30;j++) 40 { 41 if (a[i]&(1<<j)) hus[j][++hut[j]]=i; 42 else if (hut[j]) lch[i]=max(lch[i],hus[j][hut[j]]); 43 } 44 if (lch[i]<lmax[i]) lch[i]=lmax[i]-1; 45 } 46 memset(hut,0,sizeof(hut)); 47 for (int i=n;i>=1;i--) 48 { 49 rch[i]=n+1; 50 for (int j=0;j<=30;j++) 51 { 52 if (a[i]&(1<<j)) hus[j][++hut[j]]=i; 53 else if (hut[j]) rch[i]=min(rch[i],hus[j][hut[j]]); 54 } 55 if (rch[i]>rmax[i]) rch[i]=rmax[i]+1; 56 } 57 LL ans=0; 58 for (int i=1;i<=n;i++) 59 ans+=1ll*(rmax[i]-rch[i]+1)*(i-lmax[i]+1)+1ll*(rmax[i]-i+1)*(lch[i]-lmax[i]+1) 60 -1ll*(rmax[i]-rch[i]+1)*(lch[i]-lmax[i]+1); 61 // for (int i=1;i<=n;i++) cout<<i<<' '<<lmax[i]<<' '<<lch[i]<<' '<<rmax[i]<<' '<<rch[i]<<endl; 62 printf("%I64d ",ans); 63 return 0; 64 }