D题：
题目大意：在一组数列中选择两个数，使其可以构成"wave"的最大长度，比如说对于数列1 2 1 3 2
选择12的话，不要看3，这两个数字可以构成的“”wave“”最大长度为4，对于数列1 2 1 1 2 可以构成的最大长度也是4 ，对于选择好的数，我们可以选择性的保留，也就是说我们可以舍弃一个1..（没读懂题意，wa了好几发）
思路：记录每个数字出现的位置，然后暴力枚举每一种情况，然后取最大。（听说正解是dp）
ACcode
#include<bits/stdc++.h> using namespace std; const int N=1E2+7; vector<int >ve[N]; int check(int a,int b){ int i=1,ja=0,jb=0,j=-1; int aa=ve[a].size(); int bb=ve[b].size(); int ans=0; while(1){ if(i&1){ while(ja<aa&&ve[a][ja]<j){ ja++; } if(ja==aa) break; j=ve[a][ja]; ans++; } else { while(jb<bb&&ve[b][jb]<j){ jb++; } if(jb==bb) break; j=ve[b][jb]; ans++; } i++; } return ans; } int main(){ int n,m; scanf("%d%d",&n,&m); int a; for(int i=1;i<=n;i++){ scanf("%d",&a); ve[a].push_back(i); } int ans=0; for(int i=1;i<=m;i++){ if(ve[i].size()==0) continue ; for(int j=1;j<=m;j++){ if(ve[j].size()==0||i==j) continue ; ans=max(ans,check(i,j)); } } printf("%d\n",ans); return 0; }
https://blog.csdn.net/qq_41646772/article/details/96831855
dp解法，用一个二维数组，记录i到j的长度，从i到j的长度等以从j到i的长度+1，即dp[i][j]=d[j][i]+1
dpcode
#include<bits/stdc++.h> using namespace std; const int N=1E2+7; int dp[N][N]; int main(){ int n,m; cin>>n>>m; int ans=0; int x; for(int i=1;i<=n;i++){ cin>>x; for(int j=1;j<=m;j++){ dp[j][x]=dp[x][j]+1; if(j==x) continue ; ans=max(ans,dp[j][x]); } } cout<<ans<<endl; return 0; }
F题 记录每个字符出现的次数计即可
#include<bits/stdc++.h> using namespace std; const int N=1000; char arr[N]; int a,v,i,n; int main(){ int m; while(scanf("%d",&m)!=EOF){ a=0,v=0,i=0,n=0; scanf("%s",arr+1); int l=strlen(arr+1); for(int j=1;j<=l;j++){ if(arr[j]==‘a‘) a++; if(arr[j]==‘v‘) v++; if(arr[j]==‘i‘) i++; if(arr[j]==‘n‘) n++; } int x=a*v*i*n; int s=pow(m,4); if(x==0){ cout<<0<<"/"<<1<<endl; } else { cout<<x/__gcd(x,s)<<"/"<<s/__gcd(x,s)<<endl; } } return 0; }
G题
一开始诶读懂题意，以为是能过就过，不能过的话在南北方向的车等待。然而不是，题意是一起等待。。。（无聊至极）
二分水过
#include<bits/stdc++.h> using namespace std; const int N=1E3+7; int arr[N]; int brr[N]; int n,m; bool check(int s){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(arr[i]==brr[j]+s) return false; if(arr[i]<brr[j]+s) break; } } return true; } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ for(int i=1;i<=n;i++) scanf("%d",&arr[i]); for(int i=1;i<=m;i++) scanf("%d",&brr[i]); sort(arr+1,arr+1+n); sort(brr+1,brr+1+m); int l=0,r=2000; int ans=1000000; while(l<=r){ int mid=(l+r)/2; if(check(mid)){ ans=min(mid,ans); r=mid-1; } else { l=mid+1; } } printf("%d\n",ans); } return 0; }
H-RNG
打表找规律吧，，一定能找到的。。。。。
2/2 ,,3/4,,,4/6,,,5/8
//2/2 3/4 4/6 5/8 // 1 2 3 4 #include<bits/stdc++.h> using namespace std; typedef long long l const ll mod=1e9+7; ll ksm(ll n,ll m){ ll res=1; while(m){ if(m&1) res=res*n%mod; m>>=1; n=n*n%mod; } return res%mod; } int main(){ ll n; while(~scanf("%dll",&n)){ ll a=n+(ll)1 ; cout<<a*ksm((ll)2*n,mod-2)%mod<<endl; } return 0; }
I--
被这个题目卡了好久，用long double输入不对，最后用字符串输入的。。。直接保留小数点后三位就可以了，其余的不用管。
AC代码
#include<bits/stdc++.h> using namespace std; const int N=100; char arr[N]; int main(){ int t; while(scanf("%d",&t)!=EOF){ int c=0; for(int i=1;i<=t;i++){ scanf("%s",arr); int s=strlen(arr); int ans=0; for(int j=s-1;;j--){ if(arr[j]==‘.‘){ for(int k=j+1;k<s;k++){ ans*=10; ans+=arr[k]-‘0‘; } break; } } int sum=0; int x=ans%10; if(x>=0&&x<=4){ sum=ans-x; } else { sum=ans-x+10; } c+=sum-ans; } float q=1000; printf("%.3f\n",c/q); } return 0; }
J-worker
每个仓库完成的额度相同，所以想到的lcm，，，然后二分就可以了，注意l和r的取值，l最小为lcm*1,,r最大为m/lcm
注意输出格式，PE了一发
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1000+7; ll arr[N]; ll mark[N]; ll n,m; ll check(ll s){ ll sum=0; for(ll i=1;i<=n;i++){ sum+=s/arr[i]; mark[i]=s/arr[i]; } if(sum==m) return 1; if(sum>m) return 0; else return 2; } int main(){ while(~scanf("%lld%lld",&n,&m)){ for(ll i=1;i<=n;i++) scanf("%lld",&arr[i]); ll base=arr[1]; for(ll i=2;i<=n;i++){ base=base*arr[i]/__gcd(base,arr[i]); } ll l=1,r=m/base; bool flag=false ; while(l<=r){ ll mid=(l+r)/2; ll x=check(mid*base); if(x==1){ puts("Yes"); flag=true; for(ll i=1;i<=n;i++){ if(i==1) printf("%lld",mark[i]); else printf(" %lld",mark[i]); } puts(""); break; } else{ if(x==0){//人数不够 r=mid-1; } else if(x==2) {//人数太多 l=mid+1; } } } if(!flag) puts("No"); } return 0; }
原文：https://www.cnblogs.com/Accepting/p/11837966.html