A Colour the Flag
#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
char s[100][100];
int main()
{
// freopen("A.in","r",stdin);
// freopen(".out","w",stdout);
int t=read();
while(t--) {
int n=read(),m=read();
For(i,n) cin>>(s[i]+1);
char h[3]={'R','W'};
bool fl1=0,fl2=0;
For(i,n) {
For(j,m) {
if(s[i][j]==h[(i+j)&1]) fl2=1;
if(s[i][j]==h[((i+j)&1)^1]) fl1=1;
}
}
if(!fl1) {
puts("YES");
For(i,n) {
For(j,m) {
cout<<h[(i+j)&1];
}cout<<endl;
}
}
else if(!fl2) {
puts("YES");
For(i,n) {
For(j,m) {
cout<<h[((i+j)&1)^1];
}cout<<endl;
}
}else {
puts("NO");
}
}
return 0;
}
B Histogram Ugliness
#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int t,n,a[412345];
int main()
{
// freopen("B.in","r",stdin);
// freopen(".out","w",stdout);
int t=read();
while(t--) {
n=read();
For(i,n)
a[i]=read();
a[n+1]=0;
ll ans=0;
For(i,n) {
ans+=max(0,a[i]-a[i+1])+max(0,a[i]-a[i-1]);
if (a[i]>a[i+1]&&a[i]>a[i-1])
ans-=a[i]-max(a[i-1],a[i+1]);
}
cout<<ans<<endl;
}
return 0;
}
C Little Alawn’s Puzzle
#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int a[3][412345];
class bingchaji
{
public:
int father[412345],n,cnt;
void mem(int _n)
{
n=cnt=_n;
For(i,n) father[i]=i;
}
int getfather(int x)
{
if (father[x]==x) return x;
return father[x]=getfather(father[x]);
}
void unite(int x,int y)
{
x=getfather(x);
y=getfather(y);
if (x^y) {
--cnt;
father[x]=y;
}
}
bool same(int x,int y)
{
return getfather(x)==getfather(y);
}
}S;
ll work() {
int n=2,m=read();
For(i,n)For(j,m) a[i][j]=read();
For(j,m) if(a[1][j]==a[2][j]) return 0;
S.mem(m);
For(j,m) {
S.unite(a[1][j],a[2][j]);
}
ll p=1;
For(j,m) if(S.getfather(j)==j) p=p*2%F;return p;
}
int main()
{
// freopen("A.in","r",stdin);
// freopen(".out","w",stdout);
int t=read();
while(t--) {
cout<<work()<<endl;
}
return 0;
}
E Lost Tree
互動題,有n個數,每次可以詢問一個大小恰為k的子集的數的xor和。最小步數求n個數的xor和。無解輸-1.
dp, f [ i ] f[i] f[i]表示知道i個數的xor和的最小步數。
#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int f[600],pr[600];
bool b[600]={};
int need[600]={};
int main()
{
// freopen("E.in","r",stdin);
// freopen(".out","w",stdout);
int n,k;cin>>n>>k;
f[0]=0;b[0]=1;
queue<int> q; q.push(0);
while(!q.empty()) {
int now=q.front();q.pop();
Rep(t,k+1) {
int nx=now+t-(k-t);
if(now<k-t || n-now<t ||nx>n||nx<0 || b[nx]) continue;
b[nx]=1;q.push(nx);f[nx]=f[now]+1;pr[nx]=now;
}
}
// PRi(f,n)
if(!b[n]) return puts("-1"),0;
stack<int> s;
int p=n;
while(p) s.push(p),p=pr[p];
ll ans=0;
int now=0;
while(!s.empty()) {
int nx=s.top();s.pop();
// int nx=now+2*t-k;
int t=(nx-now+k)>>1;
int ad=t,de=k-t;
putchar('?');
For(i,n) {
if(!need[i]&&ad) --ad,need[i]^=1,printf(" %d",i);
else if(need[i]&&de) --de,need[i]^=1,printf(" %d",i);
}
puts("");
cout.flush();
ll p;cin>>p;ans^=p;
now=nx;
}
cout<<"! "<<ans<<endl;
return 0;
}
F2 Falling Sand (Hard Version)
在一個n*m的地圖,某些地圖有沙塊,沙塊點選會下落,每次向下移動一格依次到底。如果一個位置有下落中的沙塊,它四聯通位置的沙塊也會下落。問至少點選幾次,才能使第i列至少下落沙塊 a i a_i ai個。
如果是打算讓所有沙塊下落,可以轉化成tarjen,求最小點集使所有點集可從該點集拿。
考慮一個沙塊下落它下面一定下落,問題轉換成第i列倒數第 a i a_i ai個沙塊下落。
不難證明,每次沙塊的影響覆寫一個區間的 a i a_i ai沙塊。
題目轉化為區間覆寫問題。