\(A_1\)
核心思路
不要傻乎乎的模拟先观察性质。(2, 3) (4,5) (6,7) (8,9).
我们可以发现a的模4都是大于1的，b的都是小于。发现这个性质之后就可以写代码了。
// Problem: A1. Non-alternating Deck (easy version)
// Contest: Codeforces - Codeforces Round #850 (Div. 2, based on VK Cup 2022 - Final Round)
// URL: https://codeforces.com/contest/1786/problem/A1
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
void solve()
{
int n;
cin>>n;
int round=1;
int a=0,b=0;
while(n>=0)
{
if(round%4<=1)
a+=min(n,round);
else
b+=min(n,round);
n-=round++;
}
cout<<a<<" "<<b<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
\(A_2\)
核心思路
还是得秉承着多发现性质，少动点脑子的原则。
这里的我们发现a开头都是白的，b开头都是黑的。这个性质就方便我们分配黑白的棋子对于每一组。然后我们可以发现每一组增加的棋子数目也是符合等差数列的。
// Problem: A2. Alternating Deck (hard version)
// Contest: Codeforces - Codeforces Round #850 (Div. 2, based on VK Cup 2022 - Final Round)
// URL: https://codeforces.com/contest/1786/problem/A2
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
void solve()
{
int n;
cin >> n;
int A0 = 0, A1 = 0, B0 = 0, B1 = 0, draw = 1, round = 1;
while(n > 0) {
int v = min(draw, n);
if(round & 1) {
A0 += (v + 1) / 2;
A1 += v / 2;
} else {
B0 += v / 2;
B1 += (v + 1) / 2;
}
n -= v;
draw += 4;
round ^= 1;
}
cout << A0 << ' ' << A1 << ' ' << B0 << ' ' << B1 << '\n';
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
B
这个题目主要是需要挖掘出来我们一个区间的移动范围：\([ra-rb,la-lb]\)(因为这个需要我们把蛋糕全部都覆盖).然后取区间的交集就好了。
// Problem: B. Cake Assembly Line
// Contest: Codeforces - Codeforces Round #850 (Div. 2, based on VK Cup 2022 - Final Round)
// URL: https://codeforces.com/contest/1786/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
void solve()
{
int n,w,h;
cin>>n>>w>>h;
vector<int> a(n+1);
vector<int> b(n+1);
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
cin>>b[i];
int L=-1e18,R=1e18;
for(int i=0;i<n;i++)
{
int x1=a[i]-w;
int y1=a[i]+w;
int r1=b[i]-h;
int r2=b[i]+h;
int l=r2-y1;
int r=r1-x1;
L=max(L,l);
R=min(R,r);
}
if(L<=R)
{
YES
}
else
{
NO
}
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
C
核心思路
我们可以发现1 2 3 4 5....这样的序列是最好的因为使用一次魔法2就好了。当然其中的元素也是可以有重复的。所以我们可以定义now为当前可以杀死怪物的生命值，当\(now\le a[i]\)的时候我们就可以增加now了。
// Problem: C. Monsters (easy version)
// Contest: Codeforces - Codeforces Round #850 (Div. 2, based on VK Cup 2022 - Final Round)
// URL: https://codeforces.com/contest/1786/problem/C
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
void solve()
{
int n;
cin>>n;
vector<int> a(n);
int now=1;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a.begin(),a.end());
/* for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;*/
int sum=0;
for(int i=0;i<n;i++)
{
cout<<now<<" ";
if(a[i]<now)
continue;
sum+=a[i]-now;
now++;
}
cout<<endl;
cout<<sum<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
D
核心思路
这个其实就是一个模拟题。
我们可以知道再某一行一个字母多了需要替换为另外一行的某个字母，并且另外一行刚好也缺少这么一个的时候。那么替换就是合法的，也就是\(w->n|n->w\).
还有一种情况就是三者成环那么就也是可以替换的，比如\(w->n,n->i,i->w\).可以先将1 3替换，然后就是1 2替换。
对了还有种情况是\(w->i,i->n,n->w\).这个就是1 3,然后2 3.
要注意其他的情况比如以i开头的都是一样的，这两种情况就已经枚举完了所有的可能，因为环是具有对称性质的。
引入一个语法知识tuple其实和pair差不多，但是它可以表示多元组。
下面简述下代码框架
首先我们得把某一行缺了什么元素和多了什么元素存储起来，要注意more和less的size一定是一样的。
然后使用for循环枚举所有的情况就好了。
#include <bits/stdc++.h>
#define debug_(x) cerr << #x << " = " << x << ' '
#define debug(x) cerr << #x << " = " << x << '\n'
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
auto id = [&](char ch) {
if(ch == 'w') return 0;
if(ch == 'i') return 1;
if(ch == 'n') return 2;
return -1;
};
auto di = [&](int v) {
if(v == 0) return 'w';
if(v == 1) return 'i';
if(v == 2) return 'n';
return 'a';
};
int T;
cin >> T;
while(T--) {
int m;
cin >> m;
vector<vector<vector<int>>> type(3, vector<vector<int>>(3));
vector<tuple<int, char, int, char>> ans;
for(int i = 0; i < m; i++) {
string s;
cin >> s;
for(int j = 0; j < 3; j++) {
s[j] = id(s[j]);
}
vector<int> more, less;
for(int j = 0; j < 3; j++) {
int v = count(s.begin(), s.end(), j);
if(v == 0) less.push_back(j);
for(int k = 2; k <= v; k++) more.push_back(j);
}
for(int j = 0; j < (int)more.size(); j++) {
type[more[j]][less[j]].push_back(i);
}
}
for(int i = 0; i < 3; i++) {
for(int j = i + 1; j < 3; j++) {
while(!type[i][j].empty() && !type[j][i].empty()) {
ans.push_back({type[i][j].back(), di(i), type[j][i].back(), di(j)});
type[i][j].pop_back();
type[j][i].pop_back();
}
}
}
while(!type[0][1].empty() && !type[1][2].empty() && !type[2][0].empty()) {
ans.push_back({type[0][1].back(), di(0), type[1][2].back(), di(1)});
ans.push_back({type[1][2].back(), di(0), type[2][0].back(), di(2)});
type[0][1].pop_back();
type[1][2].pop_back();
type[2][0].pop_back();
}
while(!type[0][2].empty() && !type[2][1].empty() && !type[1][0].empty()) {
ans.push_back({type[0][2].back(), di(0), type[2][1].back(), di(2)});
ans.push_back({type[2][1].back(), di(0), type[1][0].back(), di(1)});
type[0][2].pop_back();
type[2][1].pop_back();
type[1][0].pop_back();
}
cout << ans.size() << '\n';
for(auto [a, b, c, d] : ans) {
cout << a + 1 << ' ' << b << ' ' << c + 1 << ' ' << d << '\n';
}
}
return 0;
}