CF978

A. Bus to Pénjamo（模拟）

题意：大巴有r排，每排2个座位，另一个家庭成员与他们坐在同一排或独自坐一排则幸福，最多有多少人感到幸福

代码：

#include<bits/stdc++.h>
using namespace std;
int a[510];
int main(){int t;cin>>t;while(t--){int n,r;cin>>n>>r;for(int i=1;i<=n;i++)cin>>a[i];int ans=0,cnt=0;//cout<<"**********\n";for(int i=1;i<=n;i++){//cout<<"&\n";if(a[i]%2==0){ans+=a[i];r-=(a[i]/2);}else{ans+=(a[i]-1);r-=(a[i]/2);cnt++;}}if(cnt<r){ans+=cnt;}else{ans+=(2*r)-cnt;}//if(r!=0)ans+=cnt%r;cout<<ans<<endl;}return 0;
}

B. Kar Salesman（贪心）

题意：有n种车，第i种型号车有ai辆，每次至多买x辆不同的车，至少多少人才能卖完这些车

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){int n,x;cin>>n>>x;ll a[n+10];ll sum=0,ma=0;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];ma=max(ma,a[i]);}cout<<max(ma,(sum+x-1)/x)<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)sol();return 0;
}
​

C. Gerrymandering（dp）

题意：有2×n的网格，它分成连通的3个一组，每个组有超过两个投给A即投给A了，最终投给A的组最多有多少

分析：一共有七种方式，初始dp00=0，终点dp0n，用check函数判断区域内是否超过两个A

代码：

#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) {//判断是否有两个'A'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;//dp[i][j] 表示到达第 i 行，第 j 列时，阿尔瓦罗能获得的最大票数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])  //### 2+ check(s[1][i], s[1][i + 1], s[1][i + 2]));         //###
​dp[0][i + 1] = max(dp[0][i + 1],                                        //## 4dp[0][i] + check(s[0][i], s[1][i], s[0][i + 1]));    //#.
​dp[1][i + 1] = max(dp[1][i + 1],                                        //#. 7dp[0][i] + check(s[0][i], s[1][i], s[1][i + 1]));    //##
​} else if (i % 3 == 1) {//和前面还有1列的关系 必然是3整数倍+1if (i + 3 < n) {//若为倒数三个 必然不符合分割规律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])  //.### 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])      //###. 1+ check(s[1][i + 1], s[1][i + 2], s[1][i + 3]));         //.###}dp[0][i + 2] = max(dp[0][i + 2],                                                //.# 6dp[0][i] + check(s[1][i], s[1][i + 1], s[0][i + 1]));        //##
​dp[0][i + 2] = max(dp[0][i + 2],                                                //## 5dp[1][i] + check(s[0][i], s[0][i + 1], s[1][i + 1]));        //.#}}cout << dp[0][n] << endl;
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t;cin >> t;while (t--) {solve();}return 0;
}

D1. Asesino (Easy Version)

题意：有一个内鬼，若干个好人和坏人，你忘记某人的身份，可以询问别人她是否为好人，1是好人，0不是好人

分析：好人认为坏人是0 坏人认为好人是0 好人认为内鬼是1 内鬼认为好人是0 内鬼认为坏人是1 坏人认为内鬼是0

代码：

#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() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t;cin >> t;while (t--) {solve();}return 0;
}