2020寒假 SWJTU 校队寒假选拔赛第一场 题解
剪枝剪去我们的疯狂/ SPFA告诉我前途在何方/ 01背包装下了忧伤/ 笑颜 洋溢脸庞
A.切割数列
描述
给你一个正整数n.
以及一个整数序列a[1..n].
现在,你需要决定是否要在a[i]和ai+1切割一次,使得这个序列分成若干个序列。
且要求,全部切割完以后,每个序列中,奇数和偶数出现的次数都是一样的.
如{1,2,3,4}可以切割一次变成{1,2}{3,4}两个序列,且每个序列中奇数和偶数出现的次数都是一样的为1.
每切割一次的代价是|a[i]-a[i+1]|.
问你在不超过B代价的情况下,你最多能对这个序列切割几次?
输入
输入的第一行为两个整数n(2<=n<=100),B(1<=B<=100).
第二行n个整数,表示a1..n.
保证初始序列中,奇数和偶数出现的次数都是一样的。
输出
输出只有一个整数,表示最多能对这个序列切割的次数.
思路
首先考虑在什么样的地方可以切，也就是从左往右扫，当扫到某个位置扫过的奇数偶数个数相同，就可以切割，统计出所有可切割的位置之后，再根据贪心，判断能够切几次即可。
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+10;
int a[maxn],b[maxn];
int main(){
int n,k;
scanf("%d%d",&n,&k);
int jj=0,od=0,cnt=1;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<n;i++){
if(a[i]%2==0){
od++;
}
else jj++;
if(jj==od){
b[cnt]=a[i]-a[i+1];
if(b[cnt]<0) b[cnt]=b[cnt]*(-1);
cnt++;
}
}
cnt--;
sort(b+1,b+cnt+1);
int ans=0;
for(int i=1;i<=cnt;i++){
if(k>=b[i]){
ans++;
k-=b[i];
}
}
printf("%d",ans);
return 0;
}
B.超级号码
描述
最近小A得到了一串号码——一个包含了 n 个数字 a_1 a_2 ... a_n的数列。小A认为一个数列是超级号码，如果它能被分为两个或更多的有相同值的部分。例如,号码350178 是超级号码因为它可以被分为三个部分350, 17 和 8: 3+5+0=1+7=8。每一个数字只能属于一个部分 。
帮小A看看他的号码是不是超级号码。
输入
第一行包含一个整数 n (2 <= n <= 100) — 号码的数字个数
第二行包含 n 个数字 a_1 a_2 ... a_n (0 <= a_i <= 9) — 小A的号码. 数字间没有空格。
输出
如果是超级号码则输出 "YES", 否则输出 "NO" (不带引号)。
思路
枚举分成的每一部分和为多少，判断是否能成立即可。
代码
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100+10;
char a[maxn];
int n,sum=0;
int keller(){
int ke=0,ls=sum/2;
for(int i=0;i<=ls;i++){
int s=0;
if(ke)
return 1;
for(int j=0;j<n;j++){
s+=a[j]-'0';
if((a[j]-'0')>i||s>i)
break;
if(s==i){
ke=1;s=0;
}
}
if(s!=0){
ke=0;
}
}
return ke;
}
int main(){
cin>>n;
scanf("%s",a);
for(int i=0;i<n;i++){
sum+=(a[i]-'0');
}
if(keller())
cout<<"YES";
else
cout<<"NO";
return 0;
}
C.三角形
描述
请你找到三个点(x1,y1),(x2,y2),(x3,y3).
其中0<=x1,x2,x3<=n,0<=y1,y2,y3<=m.
每个点的坐标值都要为整数.
使得这3个点组成的三角形的面积等于n*m/k.
输入
输入只有一行,3个正整数n,m,k(1<=n,m<=10^9,2<=k<=10^9).
输出
如果找不到,输出"NO".
否则输出一行"YES".
然后紧接着3行,每一行两个整数表示xi,yi.
如果有多个答案,可以任意输出其中一组
思路
假设一个点是原点的话，三个点的坐标就是 (0,0)、(x,0)、(0,y)
又xy/2=nm/k
令x=n/k/gcd(2m,k),y=2m/gcd(2m,k)构造即可
代码
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }
int main(){
ll n,m,k;
cin>>n>>m>>k;
if((2*n*m%k)!=0){
cout<<"NO";
return 0;
}
int ke=1;
if((k&1)==0)
k/=2;
else ke=0;
ll ggg=gcd(n,k);
ll x=n/ggg;k/=ggg;
ll y=m/k;
if(ke==0){
if(ggg>=2)
x*=2;
else
y*=2;
}
cout<<"YES"<<endl;
cout<<0<<' '<<0<<endl;cout<<x<<' '<<0<<endl;cout<<0<<' '<<y<<endl;
return 0;
}
D.采蘑菇
描述
赵老师降落在火星上的一片森林中，他想要带一些资源回地球进行研究
森林由两行组成，每行可分为n个连续空格。对于每个空格，赵老师都知道资源在这个空格中的生长速度（即每分钟在这个空格中生长多少克资源）。
赵老师可以用1分钟从一个格子移动到另一个相邻的格子中。赵老师不能离开这片森林。
如果两个单元格共用一个边，则认为它们是相邻的。
当赵老师进入某个格子中时，他将立即收集完所有生长在那里的资源。
赵老师从左上角的格子开始他的旅程。赵老师每分钟都必须移动到相邻的格子中，他不能等待资源生长。
他只想进入每个格子一次，并最大化收集到的资源的总重量。
最初，所有格子中的资源都是0。注意，赵老师不需要返回起始格子，且必须经过每一个格子一次。
求出最大总重量
输入
第一行包含一个正整数n (1 ≤ n ≤ 3·105) — 格子的长度.
第二行有 n个正整数 a1, a2, ..., an (1 ≤ ai ≤ 106) — 第一行中每个格子的生长速率.
第三行包含 n 个正整数 b1, b2, ..., bn (1 ≤ bi ≤ 106) — 第二行中每个格子的生长速率.
输出
输出一个整数 — 赵老师能采集到的最大资源量. 注意，每个格子赵老师最多且必须经过一次！
思路
因为格子是两行的，所以可以发现对于从某个节点停止的情况，路线有很大的规律，维护前缀和处理即可
代码
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=300000+5;
ll a[2][maxn],pre[2][maxn];
ll suf[2][maxn],ipre[2][maxn],isuf[2][maxn];
int n;
int main(){
scanf("%d",&n);
ll sum1=0;
for(int i=0;i<2;i++){
for(int j=1;j<=n;j++){
scanf("%lld", &a[i][j]);
sum1+=a[i][j];
}
}
for(int i=0;i<2;i++){
for(int j=1;j<=n;j++) {
pre[i][j]=pre[i][j-1]+a[i][j];
ipre[i][j]=ipre[i][j-1]+pre[i][j];
}
}
for(int i=0;i<2;i++){
for(int j=n;j>=1;j--){
suf[i][j]=suf[i][j+1]+a[i][j];
isuf[i][j]=isuf[i][j+1]+suf[i][j];
}
}
bool isup=0;
ll sum=0,mx=-1e15;
for(int i=1;i<=n;i++){
if(isup==0){
sum+=1ll *(2*i-1)*a[0][i];
sum+=1ll *(2*i)*a[1][i];
mx=max(mx,sum+isuf[1][i+1]+2ll *i*suf[1][i+1]+(ipre[0][n]-ipre[0][i])-pre[0][i]* 1ll *(n-i)+(n+i)*suf[0][i+1]);
isup=1;
}
else if(isup==1){
sum+= 1ll *(2*i)*a[0][i];
sum+= 1ll *(2*i-1)*a[1][i];
mx=max(mx,sum+isuf[0][i+1]+ 2ll *i*suf[0][i+1]+(ipre[1][n]-ipre[1][i])-pre[1][i]*1ll*(n-i)+(n+i)*suf[1][i+1]);
isup=0;
}
}
sum=0;
for(int i=1;i<=n;i++)
sum+=i*a[0][i];
for(int i=n;i>=1;i--)
sum+=(n+(n-i+1))*a[1][i];
mx=max(mx,sum);
printf("%lld",mx-sum1);
return 0;
}
E.矩阵
描述
现在小A正在参加一场数学考试。 为了赢得高分，小A想要猜出卷子里的矩阵!
小A只知道这个矩阵有n 行和m 列.。每一行, 他知道所有元素的异或之值。序列a1, a2, ..., an 分别代表第 1, 2, ..., n行所有元素的异或值. 同样的, 对每一列, 他也知道每一列所有元素的异或值。 序列b1, b2, ..., bm 分别代表第1, 2, ..., m列所有元素的异或值。
帮助小A找到一个符合条件的矩阵，或告诉他不存在这样的矩阵。
输入
第一行为两个整数n 和 m (2 ≤ n, m ≤ 100) — 矩阵的行数和列数。
第二行为n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 109), 其中 ai 是每一行所有元素的异或值 i。
第三行有m 个整数 b1, b2, ..., bm (0 ≤ bi ≤ 109), 其中 bi是每一列所有元素的异或值 i。
输出
如果没有符合条件的矩阵，输出 "NO"（不加引号）。
否则, 第一行输出 "YES", 然后接下来的n行m 列输出ci1, ci2, ... , cim (0 ≤ cij ≤ 2·109) — 即符合条件的矩阵。
如果有多个矩阵符合条件，输出任意一个。
思路
我们知道
行异或和：suma = a[1]^a[2]^a[3]...^a[n].
列异或和：sumb = b[1]^b[2]^b[3]...^b[m].
这道题的判断为YES的充要条件就是：suma = sumb
由异或和的算法：x^a = b <==> x^b = a 知：
a[1]^a[2]^a[3] ... ^a[n-1] = a[n]^suma
b[1]^b[2]^b[3] ... ^b[m-1] = b[m]^sumb
------------------------| .
------------------------| .
------------------------O ---x
比如这两条线的交点为x 则要找到一个x(a[n]=b[m])使他满足：
x^a[1]^a[2]^a[3]^ ... ^a[n-1] = b[m]且
x^b[1]^b[2]^b[3]^ ... ^ b[m-1] = a[n]
也就是 x^suma^a[n] = b[m], 故 x = suma^a[n]^b[m].
代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100+10;
int a[maxn],b[maxn];
int n,m,ke1,ke2;
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ke1 ^=a[i];
}
for(int i=1;i<=m;i++){
scanf("%d",&b[i]);
ke2 ^=b[i];
}
if(ke1 ^ ke2){
printf("NO");
return 0;
}
else
printf("YES\n");
for(int i=1;i<=n-1;i++){
for(int j=1;j<=m-1;j++){
printf("0 ");
}
printf("%d\n",a[i]);
}
for(int i=1;i<=m-1;i++){
printf("%d ",b[i]);
}
int ans=b[m];
for(int i=1;i<n;i++){
ans^=a[i];
}
printf("%d",ans);
return 0;
}
F.宇航员
描述
蕾蕾书记正计划带他的team——n个人去火星探险。其中最重要的任务是为队员提供食物。 仓库每天有m袋食物。每袋中都有一些ai类型的食物。 每位队员每天只吃一袋食物。由于极端的负荷，每个队员必须在整个探险过程中吃相同类型的食物。不同的队员可能会吃不同(或相同)类型的食物。 也就是说，对于每个队员j，蕾蕾书记应该选择他的食物类型bj，队员j每天会吃一个bj类型的食物包。不同队员的bj值可能不同。 按照上述要求，考察的最长可能天数是多少天?
输入
第一行包含两个整数n和m (1≤n，m≤100)队员的数量，可用的食品包的数量。 第二行包含整数序列a1,a2,…,am(1≤ai≤100), ai是i食品包的类型。
输出
输出一个整数——考察可以持续的天数。如果连一天都坚持不下去，输出0。
思路
枚举最长天数即可
代码
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=100+10;
int a[maxn];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x;
cin>>x;
a[x]++;
}
for(int i=1;i<=m+1;i++){
int cnt=0;
for(int j=0;j<=100;j++){
cnt+=a[j]/i;
}
if(cnt<n){
cout<<i-1;
break;
}
}
return 0;
}
H.最大匹配
描述
给n个block，每个block表示为 [color1 | value | color2] 需要找出一个值最大的block序列，block序列的值定义为内部所有block的value和。一个block序列里，需要满足每个block的左颜色与左边元素的右颜色相同，每个block的左颜色和右颜色可以互换
输入
第一行输入n(1<=n<=100)
接下来n行 每行包含一个block的信息 color1, value, color2 (1<=color1,color2 <= 4, 1<=value <= 100000)
输出
输出最大的序列值
思路
这题正解应该是跑个欧拉图什么的，但是数据范围比较小，用暴力dp也可以,至于怎么dp由于过于暴力详见代码233333
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+10;
int f[maxn][maxn][5][5];
int main(){
int n,ans=0;
cin>>n;
memset(f,-0x3f,sizeof(f));
for(int i=1;i<=n;i++){
int a,b,c;
cin>>a>>c>>b;
f[i][i][a][b]=f[i][i][b][a]=c;
}
for(int i=n;i;i--){
for(int j=i;j<=n;j++){
for(int x=1;x<=4;x++){
for(int y=1;y<=4;y++){
for(int k=i;k<=j+1;k++){
f[i][j][x][y]=max(f[i][j][x][y],max(f[i][k][x][y],f[k+1][j][x][y]));
for(int p=1;p<=4;++p){
f[i][j][x][y]=max(f[i][j][x][y],max(f[i][k][p][y]+f[k+1][j][x][p],f[i][k][x][p]+f[k+1][j][p][y]));
}
}
ans=max(ans,f[i][j][x][y]);
}
}
}
}
printf("%d",ans);
return 0;
}