学长学姐们觉得出测试题很有趣呢！于是刚刚返校的我们就又迎来了一次测试。
考试难度：最高为队列；
出题人：Cansult，Slr，Milky-way。
当然这个难度是不用信的，因为它并不靠谱...
T1:宽嫂的小裙子
题意概述：Cansult得到了一块m*n的布，要把它裁成一个个正方形做裙子，还要对每一块剪开的布进行锁边（只锁一边就可以），最小化这个代价。
看起来像个贪心，事实上也是，每次按照最大的裁，裁到裁完为止...答案为$a+b-gcd(a,b)$然后我就爆0啦！因为没开longlong，果然一个中考过去什么都忘了...
# include <cstdio> # include <iostream> using namespace std; int t; long long a,b,r,ans=0; int main() { freopen("skirt.in","r",stdin); freopen("skirt.out","w",stdout); scanf("%d",&t); for (int i=1;i<=t;++i) { ans=0; scanf("%lld%lld",&a,&b); if(a<b) swap(a,b); while (b!=0) { r=a/b; ans+=r*b; a=a%b; swap(a,b); } printf("%lld ",ans); } fclose(stdin); fclose(stdout); return 0; }
T2:宽嫂的缝纫
bzoj原题生成树：https://www.lydsy.com/JudgeOnline/problem.php?id=2467
算是个结论题？
最伤心的事莫过于之前见到过这道题在宽嫂博客首页，但是却没有点开看一眼...看到这道题第一感觉：Matrix-Tree定理...可是我不会。因为只是输入一个n，所以推测可能是个结论题，可是考试的时候1h也没想出来qwq
其实还是很简单的，首先有n个五边形，都是环，所以从这些环中就必须各删一条边，又因为树的性质，所以有一个环必须切两条边，（感性认识一下）如果在某一个环上删两条边，必然要删掉一条在中间的边，剩下的边就可以随便删一条了。所以选环有n种方法，删其他边又有4种方法，最终答案：$5^{n-1}*4*n$
# include <cstdio> # include <iostream> # define mod 2007 using namespace std; int n,t; long long qui(int a,int x) { long long s=1; while (x) { if(x&1) s=s*a%mod; a=a*a%mod; x=x>>1; } return s; } long long ans(int n) { long long s=n%mod; s=(s*4)%mod; s=(s*qui(5,n-1))%mod; return s; } int main() { scanf("%d",&t); for (int i=1;i<=t;i++) { scanf("%d",&n); if(n==1) printf("5 "); else printf("%lld ",ans(n)); } return 0; }
T3:宽嫂的初中回忆
题意概述：给定$a$,$b$,$c$,$k$,求$f[x]^{a}*b+c=x,0<=x<=k$的根的个数；
当然先打个暴力啦：
# include <cstdio> # include <iostream> using namespace std; int t; long long p; int a,b,c,k,f,J; int q[1000000]; int h=0,ans=0; int main() { freopen("mem.in","r",stdin); freopen("mem.out","w",stdout); scanf("%d",&t); for (int i=1;i<=t;i++) { scanf("%d%d%d%d",&a,&b,&c,&k); ans=0; for (int j=0;j<=k;++j) { f=0; J=j; while (J) { f+=J%10; J=J/10; } p=1; for (int x=1;x<=a;x++) p=(long long)p*f; p*=b; p+=c; if(p==j) ans++,q[++h]=j; } if(ans==0) { printf("0 -1 "); continue; } printf("%d ",ans); for (int j=1;j<=h;j++) printf("%d ",q[j]); h=0; printf(" "); } fclose(stdin); fclose(stdout); return 0; }
正解是枚举$f[x]$,因为$k<=10^{9}$,所以$f[x]$并不会很大。
1 # include <cstdio> 2 # include <iostream> 3 4 using namespace std; 5 6 int t; 7 int a,b,c,k; 8 long long n; 9 int q[1000000]; 10 int h=0; 11 12 int divi(int n) 13 { 14 int ans=0; 15 while (n) 16 { 17 ans+=n%10; 18 n=n/10; 19 } 20 return ans; 21 } 22 23 long long qui(int x,int n) 24 { 25 long long s=1; 26 while (n) 27 { 28 if(n&1) s=s*(long long)x; 29 x=(long long)x*x; 30 n=n>>1; 31 } 32 return s; 33 } 34 35 int main() 36 { 37 scanf("%d",&t); 38 for (int i=1;i<=t;i++) 39 { 40 scanf("%d%d%d%d",&a,&b,&c,&k); 41 h=0; 42 for (int i=0;i<=81;i++) 43 { 44 n=qui(i,a)*b+c; 45 if(n>k||divi(n)!=i) continue; 46 q[++h]=n; 47 } 48 printf("%d ",h); 49 if(h==0) 50 { 51 printf("-1 "); 52 continue; 53 } 54 for (int i=1;i<=h;i++) 55 printf("%d ",q[i]); 56 printf(" "); 57 } 58 return 0; 59 }
T4:宽嫂的军训
CQOI原题：https://www.luogu.org/problemnew/show/P1627
打了一个略微优秀的暴力水了80，赛后知道我的写法是枚举i,j，其实可以枚举i，把j的值先存起来，就可以A了，感觉很亏...
# include <cstdio> # include <iostream> using namespace std; int t; long long p; int a,b,c,k,f,J; int q[1000000]; int h=0,ans=0; int main() { freopen("mem.in","r",stdin); freopen("mem.out","w",stdout); scanf("%d",&t); for (int i=1;i<=t;i++) { scanf("%d%d%d%d",&a,&b,&c,&k); ans=0; for (int j=0;j<=k;++j) { f=0; J=j; while (J) { f+=J%10; J=J/10; } p=1; for (int x=1;x<=a;x++) p=(long long)p*f; p*=b; p+=c; if(p==j) ans++,q[++h]=j; } if(ans==0) { printf("0 -1 "); continue; } printf("%d ",ans); for (int j=1;j<=h;j++) printf("%d ",q[j]); h=0; printf(" "); } fclose(stdin); fclose(stdout); return 0; }
首先可以发现数的大小并没有想象中那么重要，事实上真正重要的是与b的大小关系。所以再读入的时候就可以预处理一下，把大于n的设为1，小于的设为-1，因为是排列没有重复元素，所以相等的也不会出现。再观察一下，发现b必须包含在这个区间中，所以就可以往两边扩展，从b往后求一个前缀和，再从b往前求一个后缀和，如果一段前缀和加一段后缀和=0，表示这一整段的中位数就是b。怎么判断呢，之前写的是枚举i，j，这个做法显然是非常愚蠢的。其实后缀和最大最小不过是$-n~n$，所以给它加上一个$n$，使其整体平移到整数部分，就可以用一个vis数组表示每种后缀出现的次数，把枚举j的复杂度降到了$O(1)$。这里还有一个小问题，题目要求长度为奇数，怎么办呢？其实这是一个不需要解决的问题，因为长度为偶数且包含b，大于b的数和小于b的数的数目相等...怎么可能呢？
# include <cstdio> # include <iostream> using namespace std; int x,n,b,pos; int a[100005]; int q1,q2; long long ans=0; int vis[300005]; int main() { scanf("%d%d",&n,&b); for (int i=1;i<=n;i++) { scanf("%d",&x); if(x>=b) a[i]++; if(x<=b) a[i]--; if(x==b) pos=i; } for (int i=pos;i<=n;i++) { q1+=a[i]; vis[q1+n]++; } for (int i=pos;i>=1;i--) { q2+=a[i]; ans+=vis[n-q2]; } printf("%lld",ans); return 0; }
T5:宽嫂的水晶项链
usaco原题：https://www.luogu.org/problemnew/show/P3143
首先从前往后扫，维护一个以i结尾的区间内，可以放到一条裙子上的最多项链，再倒着扫一次，枚举断点即可。
其实这题学姐给我们提过要做，而且也有不止一个人做了，可是为什么这次A这题的人这么少...
# include <cstdio> # include <iostream> # include <algorithm> using namespace std; long long rf,rx,a[500005],k; int n; int dp1[500005],dp2[500005]; char rc; long long read() { rc=getchar(); rf=1; rx=0; while (!isdigit(rc)) { if(rc=='-') rf=-rf; rc=getchar(); } while (isdigit(rc)) { rx=(rx<<3)+(rx<<1)+(rc^48); rc=getchar(); } return rx*rf; } int main() { freopen("crystal.in","r",stdin); freopen("crystal.out","w",stdout); scanf("%d%lld",&n,&k); for (int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+1+n); int j=1; for (int i=1;i<=n;i++) { while (a[i]-a[j]>k) j++; dp1[i]=max(i-j+1,dp1[i-1]); } j=n; for (int i=n;i>=1;i--) { while (a[j]-a[i]>k) j--; dp2[i]=max(j-i+1,dp2[i+1]); } int ans=0; for (int i=1;i<=n;i++) ans=max(ans,dp1[i]+dp2[i+1]); cout<<ans; fclose(stdin); fclose(stdout); return 0; }
T6:宽嫂的学妹
题意概述：有n块积木，每块积木的高度给出，搭两座塔，要求高度一致，求最大高度。
考到最后没有时间了，就写了一个大爆搜：
# include <cstdio> # include <iostream> using namespace std; int n; int ans=0; int a[10005]; int s[10005]; void dfs(int x,int l,int r) { if(x==n+1) { if(l==r) ans=max(ans,l); return ; } if(l+s[x]<r) return; if(r+s[x]<l) return; dfs(x+1,l+a[x],r); dfs(x+1,l,r+a[x]); dfs(x+1,l,r); } int main() { // freopen("cxy.in","r",stdin); // freopen("cxy.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=n;i>=1;i--) s[i]=s[i+1]+a[i]; dfs(1,0,0); if(ans==0) printf("Impossible"); else printf("%d",ans); // fclose(stdin); // fclose(stdout); return 0; }
正解是dp,$f[i][j]$表示用前$i$块积木，两塔高度差为$j$时低塔的高度，还可以把第一维省掉。
注意不要用不合法的情况进行转移。
# include <cstdio> # include <iostream> using namespace std; int x,n,b,pos; int a[100005]; int q1,q2; long long ans=0; int vis[300005]; int main() { scanf("%d%d",&n,&b); for (int i=1;i<=n;i++) { scanf("%d",&x); if(x>=b) a[i]++; if(x<=b) a[i]--; if(x==b) pos=i; } for (int i=pos;i<=n;i++) { q1+=a[i]; vis[q1+n]++; } for (int i=pos;i>=1;i--) { q2+=a[i]; ans+=vis[n-q2]; } printf("%lld",ans); return 0; }
转移有四种情况：
1.不放：$dp[i][j]=dp[i-1][j]$
2.放在高的上： $dp[i][j]=dp[i-1][ j-a[i] ]+a[i] , j>=a[i]$
3.放在矮的上且没有超过高的:$dp[i][j]=dp[i-1][ j+a[i] ]$
4.放在矮的上并使得矮的将高的取而代之：$dp[i][j]=dp[i-1][ a[i]-j ]+j$
这么看来还是很简单的，之前没做出来是想偏了，以为要保存两个塔的高度，现在发现没有必要，只要保留相对高度就行。
预计得分：100+0+40+（50~60）+100+（0~100）=240+（50~160）
实际得分：0+0+40+80+100+50=270
于是考完就很绝望啊...于是就等到打上课铃的时候才终于进教室，讲题的时候发生了很多奇妙的事情，学会了教师机暴政的n种方法。
最后%一下rk2的博客：https://www.luogu.org/blog/user35178/cansult-di-du-liu-ce-shi。
事实上这次测试还是很棒的！如果不考这个我们也许已经在矩乘和期望dp的水深火热中挣扎了...