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 tcin>>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;
}
