A：题意是给定n，k，求一个包含n个正整数的序列，满足序列和能够整除k，输出该序列最小的最大值。
如果n<=k，res等于k/n+(k%n != 0)
如果n>k，那么需要将k乘上一个数z，使得k>=n。而这个z=n/k+(n%k != 0)，之后再进行上述操作。
1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 using namespace std; 5 const int N=110; 6 double a[N],pre[N]; 7 int main(void){ 8 int t; 9 cin>>t; 10 while(t--){ 11 int n,k; 12 cin>>n>>k; 13 k=k*(n/k+(n%k!=0)); 14 int res=k/n; 15 if(k%n){ 16 res++; 17 } 18 cout<<res<<endl; 19 } 20 return 0; 21 }
B：给定一个包含n个数的序列，和一个整数k，定义了一个概念 inflation coefficients 表示a[ i ] / (a[ 0 ] +a [ 1 ] +...+ a [ i-1 ] = a [ i ] / pre [ i-1 ] 。你可以增加序列a中的某一个数，来保证任何一个 inflation coefficients都小于等于k%，求最小的改变是多少。
我们可以发现，当某一个 inflation coefficients > k % 时，我们可以直接增加第一个值，来保证他小于k%，正确性是显然的，那么我们就可以在线性的时间内求得答案。
1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 using namespace std; 5 typedef long long LL; 6 const int N=110; 7 LL a[N],pre[N]; 8 int main(void){ 9 int t; 10 cin>>t; 11 while(t--){ 12 int n,k; 13 cin>>n>>k; 14 for(int i=1;i<=n;i++){ 15 cin>>a[i]; 16 pre[i]=pre[i-1]+a[i]; 17 } 18 LL res=0,sum=a[1]; 19 for(int i=2;i<=n;i++){ 20 if(a[i]*100>k*(pre[i-1]+res)){ 21 LL delta=(100*a[i]-k*(pre[i-1]+res)+k-1)/k;//+ k-1 是用于向上取整 22 res+=delta; 23 } 24 } 25 cout<<res<<endl; 26 } 27 return 0; 28 }
C：题意为给定n条长度为已知的链条，每一条节点从1开始编号，再给定每一条链的首尾连接在前一条链的哪个端点上（1除外）。求最大的环的边数。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int N=1e5+10; 5 LL f[N]; 6 LL c[N],a[N],b[N]; 7 void solve(){ 8 memset(f,0,sizeof f); 9 int n; 10 cin>>n; 11 for(int i=1;i<=n;i++) cin>>c[i]; 12 for(int i=1;i<=n;i++) cin>>a[i]; 13 for(int i=1;i<=n;i++) cin>>b[i]; 14 LL res=0; 15 for(int i=2;i<=n;i++){ 16 LL t=abs(a[i]-b[i]); 17 if(t==0){ 18 f[i]=c[i]-1+2; 19 }else{ 20 f[i]=max(c[i]-1+2+f[i-1]-t , c[i]-1+2+t); 21 } 22 res=max(res,f[i]); 23 } 24 cout<<res<<endl; 25 } 26 int main(void){ 27 int t; 28 cin>>t; 29 while(t--){ 30 solve(); 31 } 32 return 0; 33 }