原题链接:Codeforces Round #696 (Div. 2)
A. Puzzle From the Future
显然直接枚举每一位,能填1就填1.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 1e5+7;
char s[N],ans[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
scanf("%s",s + 1);
int last = -1;
forn(i,1,n)
{
int c = s[i] - '0';
if(c + 1 == last) ans[i] = '0',last = c;
else ans[i] = '1',last = c + 1;
}
forn(i,1,n) printf("%c",ans[i]);
puts("");
}
return 0;
}
B. Different Divisors
显然取最近质数
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 1e6+7;
int primes[N],cnt;
bool st[N];
void init(int N)
{
for(int i = 2;i <= N;++i)
{
if(!st[i]) primes[cnt++] = i;
for(int j = 0;j < cnt && primes[j] * i <= N;++j)
{
st[primes[j] * i] = 1;
if(i % primes[j] == 0)
{
break;
}
}
}
}
int main()
{
init(N - 1);
int T;scanf("%d",&T);
while(T--)
{
ll d;scanf("%lld",&d);
int cur = 1;
forn(i,0,cnt - 1)
{
if(cur == 1)
{
if(primes[i] - cur >= d)
cur = primes[i];
}
else if(primes[i] - cur >= d)
{
printf("%lld
",1ll*primes[i] * cur);
break;
}
}
}
return 0;
}
C. Array Destruction
题目大意:给定一个长度为(2*n)的数组,再最开始,选定一个数(x),接下来执行若干步操作:选定数组中两个不同位置的元素,且和为(x).将两者从数组中删除,并更新(x)为两者中的较大者.问是否能删除整个数组,如果可以,输出一组可行的方案,如果不能输出无解.
思路
不妨把每个数对写作((x,y))并且保证(xgeq y).显然可以注意到的是每一步操作之后,势必会让一开始选定的(x)的值变小,记作(x_1),那么显然(x_1)必须要是整个数组的最大值,因为每次操作之后都会变小,变小之后不可能再消除最大值.
现在的问题是,已知(x1),(y1)未知,其次((x2,y2))等等之后的未知,需要求一组可行的方案满足每一组(x_i+y_i=x_{i-1}).逐次考虑构造,因为每次都会让最小值变小,所以一个行之有效的方案就是依次构造每个(x)的值的同时,保证选择的是整个数组中当前还没有选过的最大的数,同时直接构造出对应的(y),因为有等式限制,如果没有对应的(y)就输出无解.
考虑如何得到(y1),一个错误的想法是先不管(y1)直接从((x2,y2))开始构造,但是这样会导致多解的存在,所以正确的方式是直接枚举(y1)的取值,之后整个局面就是固定的.整个枚举和(check)的过程占到(O(n^2))所以在每次寻找最大值和找最大值的时候使用其他数据结构查询,例如(map),使查询的复杂度降到(O(logn))即可通过.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
typedef pair<int,int> pii;
#define x first
#define y second
const int N = 2005;
int a[N];
map<int,int> cnt;
inline void burn(int x)
{
if(--cnt[x] == 0) cnt.erase(x);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
cnt = map<int,int>();
int n;scanf("%d",&n);
forn(i,1,2 * n) scanf("%d",&a[i]);
sort(a + 1,a + 2 * n + 1);
int __r = 0;
for(int i = 1;i <= 2 * n - 1;++i)
{
cnt = map<int,int>();
forn(j,1,2 * n) cnt[a[j]]++;
int target = a[2 * n],y1 = a[i];
burn(a[2 * n]);burn(a[i]);
int del = 2,ok = 1;
vector<pii> op;
op.push_back({target,y1});
while(del < 2 * n)
{
auto _from = cnt.rbegin();
int x = (*_from).first;burn(x);
if(!cnt.count(target - x)) {ok = 0;break;}
op.push_back({x,target - x});
burn(target - x);
target = x;
del += 2;
}
if(!ok) continue;
printf("YES
%d
",op[0].x + op[0].y);
for(int i = 0;i < op.size();++i) printf("%d %d
",op[i].x,op[i].y);
__r = 1;
break;
}
if(!__r) puts("NO");
}
return 0;
}
D. Cleaning
题目大意:有(n)堆石子,每堆石子各有(a_i)个,每次可以选取两个相邻的且都不空的石子堆里同时拿走一个石子.如果有石子堆是空的,则相邻关系不继承.由于这个游戏太不合理了,所以给你一次机会,在游戏开始之前可以交换两个相邻的石子堆.问是否能移走所有的石子.
数据范围:
(2 leq n leq 2*10^5)
(1 leq a_i leq 10^9)
思路
由于交换的条件比较吊比,先考虑一个子问题:没有交换的时候如何判断是否存在解.
值得注意的性质是:对于(a_1)来说如果想要消除这堆石子,那么只能是让(a_1)和(a_2)相邻的去删除,删除之后会让(a_1=0,a_2-=a_1).同样的对最右端也是对称的,不难想到可以先预处理出在不使用交换的前提下,从左边往右边一个一个推,和右边往左边分别推到(i)这个位置会导致(i)这个位置上有多少个石子,分别记做(L_i,R_i).那么有了这个预处理之后,在没有交换的前提下,我们可以把左边的一段操作到(i)这个点和右边一段操作到(i)个点这两部分合起来,也就是如果从第一个元素一直往右推,从右往左一直推,假如说有解的话,那么应该有一个分界点(i)使得他俩合并起来之后有什么相等条件表示左右两边都可以删除完,比较显然就是(R_i-L_{i-1}=0).
考虑加入交换条件,因为交换只限于在两个相邻的元素之间交换,所以可以枚举任意一对数((i,i+1)),那么根据上面的分析,我们可以把左边的部分直接合并地看做是一个元素(L[i-1])右边的元素合并地看做是(R[i + 2]),而中间两个数进行交换,得到的一个等价的数组(t={L[i-1],a[i+1],a[i],R[i +2]}).只需检查这个数组是否合法就可以了.
当然,这个做法无法处理边角情况,也就是交换第一个元素和第二个元素,以及最后一个元素和倒数第二个元素.对于这两种情况可以直接提前处理.但是这样提前处理的时候又导致(n=1)的情况需要特判,继续堆一下就行了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
const int N = 2e5+7;
const ll INF = 1e18;
int a[N],b[N];
ll L[N],R[N];
bool check(vector<ll> a)
{
forn(i,1,a.size() - 1)
{
if(a[i] < a[i - 1]) return 0;
a[i] -= a[i - 1];
}
return a.back() == 0;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
vector<ll> a(n + 17,0),b(n + 17,0);
forn(i,1,n) scanf("%lld",&a[i]),b[i] = a[i];
if(n == 1)
{
puts("NO");
continue;
}
int ok = 0;
if(check(a)) ok = 1;
swap(a[1],a[2]); if(check(a)) ok = 1;swap(a[1],a[2]);
swap(a[n],a[n - 1]); if(check(a)) ok = 1;swap(a[n],a[n - 1]);
forn(i,1,n) L[i] = R[i] = -INF;
forn(i,1,n) if(b[i] < b[i - 1]) break;else L[i] = b[i] -= b[i - 1];
forn(i,1,n) b[i] = a[i];
forr(i,1,n) if(b[i] < b[i + 1]) break;else R[i] = b[i] -= b[i + 1];
forn(i,2,n - 2)
{
vector<ll> t = {L[i - 1],a[i + 1],a[i],R[i + 2]};
if(L[i - 1] == -INF || R[i + 2] == -INF) continue;
if(check(t)) {ok = 1;break;}
}
if(ok) puts("YES");
else puts("NO");
}
return 0;
}