2019 SWJTU-ACM新秀杯 预赛 题解
屏幕在深夜微微发亮/ 思想在那虚树路径上彷徨/ 平面的向量交错生长/ 织成 忧伤的网
T1 取数字
描述
给定两个长度分别为m和n的、仅由数字1-9组成的字符串。现从这两个字符串中取出总共k个数字，拼接成一个数，要求从同一个字符串中取出的数字保持其在原字符串中的相对顺序。求满足上述条件的最大的数。
输入
第一行一个整数T (1≤T≤100)，表示T组数据。
每一组数据包括3行。前两行是字符串，最后一行是一个数字k。字符串长度m、n满足1≤m,n≤303; k满足1≤k≤m+n。
输出
输出共T行，包括T个数
思路
显然n和m都不大，可以枚举第一个串取i个数，另外一个串取k-i个数，对每个字符串单独取数字找到最大的数，再把这两个数拼起来就得到了取i、k-i个数字的情况下最大的数。
对于每个字符串取i个数时，从左往右扫，每次删去非严格递减序列的最后一个数，直到剩下i个数为止。
代码
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=700;
char a[maxn],b[maxn],c[maxn],d[maxn],u[maxn],la[maxn];
int n,m;
void sel1(int x){
int p=n-x; //要删的数目
int i=0,j=-1;
while(a[i]){
while(j>=0&&p&&c[j]<a[i]){
j--;
p--;
}
j++;c[j]=a[i];i++;
}
c[x]='\0';
return ;
}
void sel2(int x){
int p=m-x;
int i=0,j=-1;
while(b[i]){
while(j>=0&&p&&d[j]<b[i]){
j--;
p--;
}
j++;d[j]=b[i];i++;
}
d[x]='\0';
return ;
}
void mer(int k){
int t=0;
int v1=0,v2=0;
while(c[v1]&&d[v2]){
u[t++]=strcmp(c+v1,d+v2)>0?c[v1++]:d[v2++];
}
if(c[v1]){
while(c[v1]){u[t++]=c[v1++];}
}
else {
while(d[v2]){u[t++]=d[v2++];}
}
int ok=0;
for(int i=0;i<k;i++){
if(u[i]>la[i]){
ok=1; break;
}
else if(u[i]<la[i]){
ok=0;break;
}
}
if(ok){
for(int i=0;i<k;i++){
la[i]=u[i];
}
}
return ;
}
int main(){
freopen("data.in","r",stdin);
freopen("aaa.out","w",stdout);
int T,k;
scanf("%d",&T);
while(T--){
memset(c,'\0',sizeof(c));
memset(d,'\0',sizeof(d));
memset(u,'\0',sizeof(u));
memset(la,'\0',sizeof(la));
scanf("%s",a);
scanf("%s",b);
scanf("%d",&k);
n=strlen(a);m=strlen(b);
for(int i=0;i<=k;i++){
memset(c,'\0',sizeof(c));
memset(d,'\0',sizeof(d));
if(i>n||k-i>m) continue;
sel1(i);
sel2(k-i);
mer(k);
}
for(int i=0;i<k;i++){
printf("%c",la[i]);
}
printf("\n");
}
}
T2 爱吃蛋糕的小生生
Description
我们都知道，小生生十分爱吃蛋糕，今天小生生参加了一个晚会，发现晚会里有n（1≤n≤10e8）个蛋糕，小生生发现蛋糕从左到右排序分别为1号，2号……n1号，2号……n号，晚会的主人小江江告诉小生生第i号蛋糕的价值为i！元，同时他会选择一些编号的蛋糕提问小生生，如果小生生能答对对应编号的蛋糕的价值能被2整除多少次，小生生就可以吃该编号的蛋糕。小生生十分想吃蛋糕，可是他的算术能力不行，现在，他想让聪明的你帮他解答一下小江江的问题。
Input
多组输入，每组第一行一个正整数T（1≤T≤100），表示小江江一共选择了T个蛋糕。接下来T行，每行表示小江江选择蛋糕的一个编号T=0时结束输入。保证输入输入的总蛋糕数量不大于10000。
Output
T行，每行一个整数，表示该编号蛋糕价值能被2整除的次数
思路
我们发现，对于数m，从从m/2+1到m数的乘积一共可以整除2的次数为m/2次，因此利用递归，就可以算出来了。
代码
#include<cstdio>
#include<iostream>
using namespace std;
int ke(int n){
if(n==0) return 0;
else return ke(n/2)+n/2;
}
int main(){
int T;
while(scanf("%d",&T)){
if(T==0)break;
while(T--){
int x;scanf("%d",&x);
printf("%d\n",ke(x));
}
}
}
T3帮他数数
描述
小A是一个卡牌游戏玩家，他现在手上有n张战斗力不同的卡片。某一天他遇到了一个任务，需要他组合出一个特定的战斗力x才能进行，然后他来寻求你的帮助。这个问题对你来说很简单，你不但能告诉他能否组出来，还能明确地告诉他有多少种方法可以完成这个组合。告诉你他每张卡的战斗力和目标战斗力c，请告诉他有多少种不同的组合方式。
输入
多组数据输入，第一行包含一个整数T(1≤T≤10)，表示有T组数据。对于每组数据：第一行包含两个整数n (1≤n≤100)，k(1≤k≤2000)，表示小A有n张卡片，他带着k个问题来找你。第二行包含n个整数ci,表示第i张卡的战斗力为c[i],保证所有c[i]的和不大于2000。第三行包含k个整数xi,表示他的第i个问题的目标战斗力x。
输出
对于每组数据，输出k行，每行包含一个整数，问题的答案对1000000007取模后的结果。
思路
背包方案数
代码
T4 不想上课
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int T; cin >> T;
while (T--){
int n, m, k; cin >> n >> m >> k;
bool ans = false;
while (k--){
int x, y; cin >> x >> y;
if(x<=5 || x>=n-4 || y<=5 || y>=m-4)
ans = true;
}
cout << (ans?"YES":"NO") << endl;
}
return 0;
}
T5 Chess Board
描述
XX有一个大小为n行m列的棋盘，但这块棋盘的格子上面不小心染上了许多不同的颜色。XX有强迫症：他希望自己的棋盘上只有一种颜色，所以他决定从原来的n行m列的棋盘上切下一块矩形的小棋盘。同时他又不想过于浪费，所以他想保证这块小棋盘的面积尽可能的大。请你帮他解决这个问题。（切割时不能破坏棋盘上每个格子的完整性）
输入
第一行一个整数T，表示测试样例个数（T≤10）。对于每个测试样例，第一行包含两个整数n，m，分别表示棋盘的行数、列数（1≤n∗m≤1e6）。接下来n行，每行一个长度为m的只包含数字(0到9)的字符串。第i行字符串中的第j个数字表示棋盘上第i行j列格子的颜色。
输出
输出一个整数，XX能切下来的小棋盘的最大面积。
思路
最大子矩阵问题，悬线法
代码
T6数 （签到题）
代码
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
struct node{
long long x,y,z;
}a[7];
int main(){
int T;
a[1].x=1;a[1].y=2;a[1].z=3;
a[2].x=1;a[2].y=3;a[2].z=2;
a[3].x=2;a[3].y=1;a[3].z=3;
a[4].x=2;a[4].y=3;a[4].z=1;
a[5].x=3;a[5].y=1;a[5].z=2;
a[6].x=3;a[6].y=2;a[6].z=1;
scanf("%d",&T);
while(T--){
long long c[4];
scanf("%lld%lld%lld",&c[1],&c[2],&c[3]);
long long maxx=c[1]+c[2]+c[3];
for(int i=1;i<=6;i++){
maxx=max(maxx,c[a[i].x]+c[a[i].y]+c[a[i].z]);
}
for(int i=1;i<=6;i++){
maxx=max(maxx,c[a[i].x]*c[a[i].y]+c[a[i].z]);
}
for(int i=1;i<=6;i++){
maxx=max(maxx,(c[a[i].x]+c[a[i].y])*c[a[i].z]);
}
for(int i=1;i<=6;i++){
maxx=max(maxx,(c[a[i].x]*c[a[i].y])*c[a[i].z]);
}
printf("%lld\n",maxx);
}
}
T7 以这样的点名有什么用呢
思路
找规律
代码
#include<cstdio>
#include<iostream>
using namespace std;
int a[1000+10][1000+10];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m,xx,yy;
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
if(a[i][j]==-1){
xx=i;yy=j;
}
}
}
int ans;
if(xx==1&&yy==1){
cout<<(-1)*(a[2][2]-a[1][2]-a[2][1])<<endl;
}
else cout<<(-1)*(a[xx-1][yy-1]-a[xx][yy-1]-a[xx-1][yy])<<endl;
}
}
T8 菜市场
描述
炉石传说中有两张卡牌，奴隶主和旋风斩。以下是两张卡的卡牌介绍：
奴隶主：奴隶主有3滴血，每当他受到伤害且不死亡就会重新生成一个新的奴隶主(3滴血)。
旋风斩：对所有随从造成1点伤害。
戴java老师是有名的炉石天才，它能够在谈笑风生间计算出场上剩余奴隶主的个数，炉石小白onsterm也想知道结果，请你帮帮他。
输入
输入有两行,第一行n,m分别代表奴隶主的个数和旋风斩的个数(1≤n≤10e5,0≤m≤10e9)。第二行n个数,a_i第i个奴隶主的剩余血量。(1≤a_i≤3)
输出
输出连续打出m个旋风斩后,剩余奴隶主的个数（结果对1000000007取模）。
思路
矩阵快速幂,设f[i]为血量为i的奴隶主个数，则一次旋风斩后有:f[1]=f[2],f[2]=f[3],f[3]=f[1]+f[2]。
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc() getchar()
#define mo 1000000007
using namespace std;
int n;
struct ahaha{
ll a[4][4];
ahaha(){
memset(a,0,sizeof a);
}
void build(){
for(int i=1;i<=4;++i)a[i][i]=1;
}
}a,b,c;
ahaha operator *(const ahaha &x,const ahaha &y){
ahaha z;
for(int k=1;k<=3;++k)
for(int i=1;i<=3;++i)
for(int j=1;j<=3;++j)
z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%mo)%mo;
return z;
}
ll k;
void init(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
int xl;
scanf("%d",&xl);
b.a[1][xl]++;
}
}
int main(){
init();
ahaha ans;ans.build();
a.a[3][3]=1;
a.a[2][1]=1;
a.a[2][3]=1;
a.a[3][2]=1;
while(k){
if(k&1)ans=ans*a;
a=a*a;k>>=1;
}
c=b*ans;
/*
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
cout<<ans.a[i][j]<<" ";
}
cout<<endl;
}
*/
ll num=c.a[1][1]+c.a[1][2]+c.a[1][3];
printf("%lld",num);
return 0;
}