第16届程序设计上海金马五校赛
A
描述
最近对抗生成网络(GAN)很火，其中有一种变体WGAN，引入了一种新的距离来提高生成图片的质量。这个距离就是Wasserstein距离，又名铲土距离。
这个问题可以描述如下:
有两堆泥土，每一堆有n个位置，标号从1~n。第一堆泥土的第i个位置有ai克泥土，第二堆泥土的第i个位置有bi克泥土。小埃可以在第一堆泥土中任意移挪动泥土，具体地从第i个位置移动k克泥土到第j个位置，但是会消耗k×|i-j|的体力。小埃的最终目的是通过在第一堆中挪动泥土，使得第一堆泥土最终的形态和第二堆相同，也就是ai=bi (1<=i<=n), 但是要求所花费的体力最小
输入测试组数T，每组测试数据,第一行输入n，1<=n<=100000,紧接着输入两行，每行n个整数，前一行为a1, a2,…,an,后一行为b1,b2,…,bn.其中0<=ai,bi<=100000,1<=i<=n
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| using namespace std; int t,n; int a[maxn],b[maxn]; int main(){ // freopen("input.txt","r",stdin); cin>>t; while(t--){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; LL ans=0; for(int i=1;i<=n;i++){ if(a[i]==b[i]) continue; int tmp=abs(a[i]-b[i]); if(a[i]>b[i]){ for(int j=i+1;j<=n;j++){ if(a[j]==b[j]) continue; else{ a[j]+=tmp; ans+=(LL)tmp*(j-i); break; } } } else{ for(int j=i+1;j<=n;j++){ if(a[j]==b[j]) continue; else{ if(a[j]>=tmp){ a[j]-=tmp; ans+=(LL)tmp*(j-i); break; } else{ tmp-=a[j]; ans+=(LL)a[j]*(j-i); a[j]=0; } } } } } cout<<ans<<endl; } return 0; }
|
思路
直接模拟 从左往后扫描 多了放到右边 不够从右边拿
F
描述
小Y在研究数字的时候，发现了一个神奇的等式方程x^2x=3x，他屈指算了一下有很多正整数x满足这个等式，比如1和2，现在问题来了，他想知道从小到大第N个满足这个等式的正整数，请你用程序帮他计算一下。
第一行是一个正整数T，表示查询次数。
接着有T行，每行有一个正整数n(n<10^12)，表示小Y的查询
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| using namespace std; int t; LL f[70],g[70]; int main(){ f[1]=1,f[2]=2; g[1]=1,g[2]=2; for(int i=3;i<=60;i++){ g[i]=g[i-1]*2; f[i]=f[i-1]+f[i-2]; } cin>>t; while(t--){ LL n; cin>>n; LL ans=0; for(int i=60;i>=1;i--){ if(n>=f[i]){ ans+=g[i]; n-=f[i]; } } cout<<ans<<endl; } }
|
思路
打表发现规律跟二进制有关 每位二进制个数的数量满足斐波拉契数列
f[i]表示二进制长度小于i-1前面所有长度的个数和 这时候答案加上的是g[i]代表一个二进制数
对于一个数n 我们根据规律从二进制头开始找1 相当于加到该数字 找到后ans+某个二进制数
I
描述
我们把十进制下每一位都是偶数的数字叫做“二数”。
小埃表示自己很聪明，最近他不仅能够从小数到大：2,3,4,5….，也学会了从大数到小：100,99,98…，他想知道从一个数开始数最少的数就得到一个二数。但是聪明的小森已经偷偷在心里算好了小埃会数到哪个二数，请你求出他要数到哪个数吧。
换句话说，给定一个十进制下最多105位的数字，请你求出和这个数字的差的绝对值最小的二数，若答案不唯一，输出最小的那个。
也就是说，给定数字n，求出m，使得abs(n-m)最小且m[i] mod 2 = 0
1 ≤ T ≤ 100, 1 ≤ n ≤ 10^100000 − 1, T组数据的数字的十进制表示长度总和不超过1000000
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| using namespace std; int t,len; string s; int check(int x){ int num=s[x]-'0'; if(num<4) return -1; else if(num>4) return 1; else if(x==len-1 && num==4) return -1; return check(x+1); } int main(){ // freopen("input.txt","r",stdin); cin>>t; while(t--){ cin>>s; len=s.length(); int up=0; for(int i=0;i<len-1;i++){ int num=s[i]-'0'; if(num&1){ if(num==9) up=-1; else up=check(i+1); if(up==-1){ s[i]=num-1+'0'; for(int j=i+1;j<len-1;j++) s[j]='8'; break; } else if(up==1){ s[i]=num+1+'0'; for(int j=i+1;j<len-1;j++) s[j]='0'; break; } } } if(len==1){ int num=s[0]-'0'; if(num&1) num--; cout<<num<<endl; continue; } if(up==0){ int num=s[len-1]-'0'; if(num&1) s[len-1]=num-1+'0'; for(int i=0;i<len;i++) cout<<s[i]; cout<<endl; continue; } if(up==1) s[len-1]='0'; else if(up==-1) s[len-1]='8'; int flag=1; for(int i=0;i<len;i++){ if(s[i]=='0' && flag) continue; flag=0; cout<<s[i]; } cout<<endl; } return 0; }
|
思路
贪心
边界在于4 少于4下降 大于4上升 若等于4 比如34的up为40 down为28 差值相等 所以继续判断下一位
若最后一位还相等 说明存在多组答案 那么选择down 因为题目要求最小
找到第一个奇数位置 判断是up还是down up后后面各位全部变成0 down后后面各位全部变成8
有多个hack点：例如0-9的数字要特判是奇还是偶 up=0代表前len-1位没有奇数 那么特判最后一位是奇还是偶
除去前两种情况后以为根据up还是down更新最后一位 输出要删去前导0
J
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
| using namespace std; int t,n,m,mid; int a[maxn],b[maxn]; int g[maxn][maxn],linker[maxn]; bool used[maxn]; void init(){ mm(g,0); for(int i=1;i<=m;i++){ for(int j=1;j<n;j++){ g[i][j]=max(abs(b[i]-a[j]),abs(b[i]-a[j+1])); } g[i][0]=abs(b[i]-a[1]); g[i][n]=abs(b[i]-a[n]); } for(int i=m+1;i<=n+1;i++){ for(int j=1;j<n;j++){ g[i][j]=abs(a[j]-a[j+1]); } } } bool dfs(int u){ for(int i=0;i<=n;i++){ if(g[u][i]<=mid && !used[i]){ used[i]=true; if(linker[i]==-1 || dfs(linker[i])){ linker[i]=u; return true; } } } return false; } int hungary(){ int ans=0; mm(linker,-1); for(int i=1;i<=n+1;i++){ mm(used,0); if(dfs(i)) ans++; } return ans; } int main(){ // freopen("input.txt","r",stdin); scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) scanf("%d",&b[i]); init(); int l=0,r=1e9,ans=0; while(l<=r){ mid=l+r>>1; int tmp=hungary(); if(tmp==n+1){ ans=mid; r=mid-1; } else l=mid+1; } printf("%d\n",ans); } return 0; }
|
思路
二分+匹配 二分最小不连贯值
n个广告有n+1个坑位 这n+1个坑位与m个广告匹配 再新建n+m-1个假广告位与n匹配 相当于这个坑位没有新广告进入
hungary跑出来的匹配如果是n+1 即全部匹配 修改二分边界
L
描述
给一个数组 a，长度为 n，若某个子序列中的和为 K 的倍数，那么这个序列被称为“K 序列”。现在要你 对数组 a 求出最长的子序列的长度，满足这个序列是 K
第一行为两个整数 n, K, 以空格分隔，第二行为 n 个整数，表示 a[1] ∼ a[n]，1 ≤ n ≤ 10^5 , 1 ≤ a[i] ≤ 10^9 , 1 ≤ nK ≤ 10^7
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| using namespace std; int n,k,a[maxn]; int dp[10000000][2]; int main(){ // freopen("input.txt","r",stdin); cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; a[i]%=k; } memset(dp,0,sizeof dp); dp[a[1]][0]=1; int now=0; for(int i=2;i<=n;i++){ now=1-now; for(int j=0;j<k;j++){ if(dp[((k+j)-a[i])%k][1-now]) dp[j][now]=max(dp[j][1-now],dp[((k+j)-a[i])%k][1-now]+1); else dp[j][now]=dp[j][1-now]; } } cout<<dp[0][now]<<endl; return 0; }
|
思路
dp 因为nk小于10^7 所以数组不能开dp[n][k] 改为滚动数组
dp的第一位代表余数 最后输出的第一位为0代表mod k等于0 即能被k整除
dp方程：若dp[x][now]由1-now推来 x的余数有两种来源 一种是dp[x][1-now] 还有一种是由该位置和前一位置的某个余数相加mod k后等于x(前提是那个数字存在) 取max即可
