Codeforces Round 998 (Div. 3) ABCD

A  模拟

思路

a1 + a2 = a3  

a2 + a3 = a4

a3 + a4 = a5

用公式计算出3个a3，再统计有几个a3 一样即可

代码

const int N = 2e3 + 10;LL aa[N];void solve()
{LL a,b,c,d;cin >> a >> b >> c >> d;aa[1] = a + b,aa[2] = c - b,aa[3] = d - c;LL ans = 0;for (int i = 1;i <= 3;i ++){LL cnt = 0;for (int j = i;j <= 3;j ++){if (aa[i] == aa[j]) cnt ++;}ans = max(ans,cnt);}cout << ans << endl;
}

B 贪心

思路

题目让找一个排列p，使得所有牛(1~n) 按照这个排序进行出牌 使得所有牛都能清空他们的牌

可以考虑

        1.先对每个牛的牌进行从小到大排序，使得自己的牌不会被自己卡(当前牌要>之前的牌)

        2.再对排序好的所有牛的第一张牌，按从小到大进行排序，排列p就是这个顺序

        3.做完1、2步骤后，出牌顺序就是最佳的顺序，如果还不能满足题意，就说明无解

代码

typedef pair<int,int> PII;const int N = 2e3 + 10;LL n,m,k;void solve()//18
{vector<int> a[N];cin >> n >> m;for (int i = 1;i <= n;i ++){for (int j = 0;j < m;j ++){int x;cin >> x;a[i].push_back(x);}}vector<PII> v;for (int i = 1;i <= n;i ++){sort(a[i].begin(),a[i].end());v.push_back({a[i][0],i});}sort(v.begin(),v.end());//按照第一张牌排序int last = -1;for (int j = 0;j < m;j ++){for (auto &[val,id] : v)//id为出牌顺序{if (a[id][j] <= last) {cout << -1 << endl;return;}else last = a[id][j];}}for (auto &[val,id] : v)cout << id <<  " "; cout << endl;}

C 思维+贪心  [看]

思路

总共偶数个数字，求满足a+b=k公式的(a,b)对的数量，因为(a,b)是偶数，所以满足要求的有偶数个，不满足要求的也有偶数个。Alice 先手，Bob 后手，看似Alice有优势，实则Bob可以掌控全局，我们可以知道，如果Alice选了一个不满足要求的数字,那么Bob可以随便选一个不满足要求的数字来匹配，反之，如果Alice选了一个满足要求的数字，则Bob可以选择满足要求的匹配的数字

所以，我们只需统计，满足要求的(a,b)的对数即可

代码

解释一下 i < (k + 1) / 2，

k = 5 , 只需统计[]内的数字 ；[1 2 ]3 4 5

k = 4  ,只需统计[]内的数字 ; [1] 2 3 4  。 因为数字2提前统计过了

LL n,m,k;void solve()
{cin >> n >> k;vector<int> a(n);for (int i = 0;i < n;i ++) cin >> a[i];vector<int> c(n + 1);for (auto i : a) c[i] ++;//每个数字出现的次数LL ans = 0;if (k % 2 == 0) ans += c[k / 2] / 2;//特判k是偶数的情况,例如k=4,有ab对(1,3),(2,2),统计2的一半即可//i就是枚举的数字for (int i = 1;i < (k + 1) / 2 && i <= n;i ++)//(a,b)成对出现,统计一半即; 因为n有奇偶情况,所以使用 i < (k + 1) / 2 取巧{if (k - i >= 1 && k - i <= n)//另一个数字满足要求ans += min(c[i],c[k - i]);}cout << ans << endl;
}

D  贪心 

思路

直接让每一个a[i]和a[i + 1]都减去较小值，再从头判断是否满足要求即可。

因为都减去，会让数字变小，为了满足不递减的要求，变小肯定比原来的好

代码

const int N = 2e5 + 10;LL n,m,k;
LL a[N];
void solve()//20
{cin >> n;for (int i = 1;i <= n;i ++) cin >> a[i];for (int i = 1;i < n;i ++){LL t = min(a[i],a[i + 1]);a[i] -= t,a[i + 1] -= t;}for (int i = 1;i < n;i ++){if (a[i] > a[i + 1]) {cout << "NO" << endl;return;}}cout << "YES" << endl;}