我的同学还在 VP，排名马上放
声明：不要觉得有 subtask 的题目只做 Easy version 没有意义，从这里也能捞很多分，况且有的时候并不是简单和难的区别，而是考不同的算法
A. Bus to Pénjamo
题意
有一辆车上面有 $r$ 排座位，每排有 $2$ 个座位，现在共 $n$ 个家庭出行坐公交车，每个家庭 $a_i$ 个人（保证 $2r\ge \sum a_i$）。
一个人感到 开心，当且仅当符合一下条件 之一：
- 他和他的家庭成员坐在一排
- 他独自一人坐在一排（旁边不能有其他人）
问最终最多有多少人 开心
思路
贪心，先让可以两个人一排的家庭成员入座，剩下的看 $[座位数]$ 与 $[剩余人数]$ 的差，得出有多少人能单独坐一排
C++ 代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,r;
void solve(){
cin>>n>>r;
int k=0;
int ans=0;
for(int i=0;i<n;i++){
int ai;
cin>>ai;
k+=(ai%2); //k表示每个家庭落单的人数
r-=(ai/2); //r最终表示还剩下几排座位
ans+=ai-ai%2;
}
r*=2; //还剩r个座位
ans+=min(r-k,k);
cout<<ans<<endl;
}
signed main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
B. Kar Salesman
题意
共有 $n$ 中型号的车，第 $i$ 种型号的车有 $a_i$ 辆，每次 $\text{Karel}$ 可以推荐别人购买至多 $x$ 辆车，且这些为 不同型号
问至少要推销给多少个人才能卖完这些车
思路
求出车数量的总和（设为 $sum$ ），和 $a_i$ 的最大值（设为 $mx$），最终答案为：$\displaystyle \max(mx,\lceil \frac{sum}{x} \rceil)$
C++ 代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n,x;
cin>>n>>x;
int mx=0,sum=0;
for(int i=0;i<n;i++){
int ai;
cin>>ai;
mx=max(mx,ai);
sum+=ai;
}
cout<<max(mx,(sum+x-1)/x)<<endl;
}
signed main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
C. Gerrymandering
题意
一个 $2*n$ 的网格图，每格代表一个居民（需要进行投票选举，可以投给 A 也可以投给 J），保证 $2n \bmod 3 =0$，将它分成 连通的 $3$ 个一组，这一组 将投给 三个人投的更多的人，如 $2$ 个 A $1$ 个 J，则这一组投给 A
问：若按最优方案分组，最终投给 $A$ 的组最多有多少
思路
需要动态规划，仅分为以下情况：
那么，只要转移正确就很简单
转移直接看代码
C++ 代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=2e9;
int n;
bool check(int a,int b,int c){
int p=(a=='A'),q=(b=='A'),r=(c=='A');
return (p+q+r>=2);
}
void solve(){
cin>>n;
string s[2];
cin>>s[0]>>s[1];
vector<vector<int> > dp(2,vector<int>(n+1,-inf));
dp[0][0]=0;
for(int i=0;i<n;i++){
if(i%3==0){
dp[0][i+3]=max(dp[0][i+3],
dp[0][i]+check(s[0][i],s[0][i+1],s[0][i+2]) //###
+check(s[1][i],s[1][i+1],s[1][i+2])); //###
dp[0][i+1]=max(dp[0][i+1], //##
dp[0][i]+check(s[0][i],s[1][i],s[0][i+1])); //#.
dp[1][i+1]=max(dp[1][i+1], //#.
dp[0][i]+check(s[0][i],s[1][i],s[1][i+1])); //##
}else if(i%3==1){
if(i<n-3){
dp[0][i+3]=max(dp[0][i+3],
dp[0][i]+check(s[0][i+1],s[0][i+2],s[0][i+3]) //.###
+check(s[1][i],s[1][i+1],s[1][i+2])); //###.
dp[1][i+3]=max(dp[1][i+3],
dp[1][i]+check(s[0][i],s[0][i+1],s[0][i+2]) //###.
+check(s[1][i+1],s[1][i+2],s[1][i+3])); //.###
}
dp[0][i+2]=max(dp[0][i+2], //.#
dp[0][i]+check(s[1][i],s[1][i+1],s[0][i+1])); //##
dp[0][i+2]=max(dp[0][i+2], //##
dp[1][i]+check(s[0][i],s[0][i+1],s[1][i+1])); //.#
}
}
cout<<dp[0][n]<<endl;
}
signed main(){
int t
cin>>t;
while(t--){
solve();
}
return 0;
}
D1. Asesino (Easy Version)
题意
这是一道 交互题
有一种游戏，共有三种角色：Knight, Knave, Impostor，可以理解为：好人、坏人和内鬼
每局游戏有 $n$ 个人，其中有 $1$ 个内鬼，若干个好人和坏人（可能 $0$ 个）
你忘记了每个人的角色，但是，你可以问玩家 $i$ ：玩家 $j$ 是不是好人？询问格式：? i j
玩家 $i$ 会回答你 1 表示是好人，0 表示不是好人
以下为不同身份的回答表格：
最多询问 $n+69$ 次，请找出内鬼是玩家几，格式为 ! i
思路
观察表格发现，若 $[i\ 认为 \ j 的身份]$ 和 $[j \ 认为\ i\ 的身份]$ 不同，那么 $i$ 和 $j$ 中必定有一个内鬼
那么我们可以问每两个相邻的人，$i$ 和 $i+1$ 互相问，$i+2$ 和 $i+3$ 互相问，以此类推，最终找到 $k$ 和 $k+1$ 不同的位置，再和其他的比较，就可以得到内鬼的位置
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n;
bool query(int a,int b){
cout<<"? "<<a<<" "<<b<<endl;
int p;
cin>>p;
cout<<"? "<<b<<" "<<a<<endl;
int q;
cin>>q;
return p!=q;
}
void solve(){
cin>>n;
int pos=-1;
for(int i=1;i<n;i+=2){
bool flag=query(i,i+1);
if(flag){
pos=i;
break;
}
}
if(pos==-1){
cout<<"! "<<n<<endl;
}else if(query(pos,pos>1?pos-1:pos+2)){
cout<<"! "<<pos<<endl;
}else{
cout<<"! "<<pos+1<<endl;
}
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}