比赛链接：https://codeforces.com/contest/2030
A. A Gift From Orangutan
肯定最小值和最大值放前面最好，答案得解
#include<iostream>#include<string.h>#include<map>#include<vector>#include<set>#include<unordered_set>#include<stack>#include<queue>#include<algorithm>#include<time.h>#include<random>#include<string>#include<string.h>#include<cctype>using namespace std;typedef long long ll;mt19937 rnd(time(0));const ll mod = 1e9 + 7;void fio(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}ll gcd(ll x, ll y){if (y == 0)return x;elsereturn gcd(y, x % y);}ll ksm(ll x, ll y){ll ans = 1;while (y){if (y & 1)ans = ans%mod*(x%mod)%mod;x = x%mod*(x%mod)%mod;y >>= 1;}return ans%mod%mod;}ll a[150000];int main(){fio();ll t;cin>>t;while(t--){ll n;cin>>n;for(ll i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);ll sum=0;for(ll i=2;i<=n;i++){sum+=a[n]-a[1];}cout<<sum<<endl;}}
B. Minimise Oneness
浅浅枚举下，发现答案不可能为0且1放在中间答案值最小为1
#include<iostream>#include<string.h>#include<map>#include<vector>#include<set>#include<unordered_set>#include<stack>#include<queue>#include<algorithm>#include<time.h>#include<random>#include<string>#include<string.h>#include<cctype>using namespace std;typedef long long ll;mt19937 rnd(time(0));const ll mod = 1e9 + 7;void fio(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}ll gcd(ll x, ll y){if (y == 0)return x;elsereturn gcd(y, x % y);}ll ksm(ll x, ll y){ll ans = 1;while (y){if (y & 1)ans = ans%mod*(x%mod)%mod;x = x%mod*(x%mod)%mod;y >>= 1;}return ans%mod%mod;}ll a[150000];int main(){fio();ll t;cin>>t;while(t--){ll n;cin>>n;for(ll i=1;i<=n/2;i++){cout<<0;}cout<<1;for(ll i=n/2+2;i<=n;i++){cout<<0;}cout<<endl;}}C. A TRUE Battle
and是优先于or的，考虑1如果在最左或者最右，一个or即可胜利，否则看是否有两个连续的1，有即胜利
#include<iostream>#include<string.h>#include<map>#include<vector>#include<set>#include<unordered_set>#include<stack>#include<queue>#include<algorithm>#include<time.h>#include<random>#include<string>#include<string.h>#include<cctype>using namespace std;typedef long long ll;mt19937 rnd(time(0));const ll mod = 1e9 + 7;void fio(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}ll gcd(ll x, ll y){if (y == 0)return x;elsereturn gcd(y, x % y);}ll ksm(ll x, ll y){ll ans = 1;while (y){if (y & 1)ans = ans%mod*(x%mod)%mod;x = x%mod*(x%mod)%mod;y >>= 1;}return ans%mod%mod;}ll a[150000];int main(){fio();ll t;cin>>t;while(t--){ll n;cin>>n;string f;cin>>f;ll pd=0;if(f[0]=='1'||f[f.size()-1]=='1')pd=1;for(ll i=0;i<f.size()-1;i++){if(f[i]=='1'&&f[i+1]=='1')pd=1;}if(pd)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}}
D. QED's Favorite Permutation
本题多个连续查询，于是得考虑连续维护；发现其实可以把数组分成多个不同得移动区间
，如果这个区间全是R或者L或者RRL这种单调的串就一定可以排好序
听说差分可以做，赛时只想到了线段树
#include<iostream>#include<string.h>#include<map>#include<vector>#include<set>#include<unordered_set>#include<stack>#include<queue>#include<algorithm>#include<time.h>#include<random>#include<string>#include<string.h>#include<cctype>using namespace std;typedef long long ll;mt19937 rnd(time(0));const ll mod = 1e9 + 7;// const ll p=rnd()%mod;void fio(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}ll gcd(ll x, ll y){if (y == 0)return x;elsereturn gcd(y, x % y);}ll ksm(ll x, ll y){ll ans = 1;while (y){if (y & 1)ans = ans%mod*(x%mod)%mod;x = x%mod*(x%mod)%mod;y >>= 1;}return ans%mod%mod;}const ll maxn = 2e5+5;
struct s
{ll l, r;ll ad, v, cf;//ad为加法的懒惰标记，cf为乘法的懒惰标记ll la;
}p[maxn << 2];
ll fa[maxn << 2];
void build(ll i, ll l, ll r)
{p[i].l = l,p[i].r = r,p[i].v = 0;p[i].la=-1;if (l == r){fa[l] = i;return;}build(i << 1, l, (l + r) >> 1);build(i << 1 | 1, ((l + r) >> 1) + 1, r);
}
void push_down(ll i)
{if (p[i].la!=-1){p[i].v=(p[i].r-p[i].l+1)*p[i].la;p[i<<1].v=(p[i<<1].r-p[i<<1].l+1)*p[i].la;p[i<<1|1].v=(p[i<<1|1].r-p[i<<1|1].l+1)*p[i].la;p[i<<1].la=p[i].la;p[i<<1|1].la=p[i].la;p[i].la=-1;}
}
void udq(ll i, ll ad, ll cf, ll l, ll r)
{if (p[i].l == l && p[i].r == r){p[i].v=ad*(r-l+1);p[i].la=ad;return;}push_down(i);ll i1 = i << 1, i2 = i << 1 | 1;if (l <= p[i1].r){if (r <= p[i1].r)udq(i1, ad, cf, l, r);elseudq(i1, ad, cf, l, p[i1].r);}if (r >= p[i2].l){if (l >= p[i2].l){udq(i2, ad, cf, l, r);}elseudq(i2, ad, cf, p[i2].l, r);}p[i].v = p[i1].v + p[i2].v;
}
ll query(ll i, ll l, ll r)
{ll ans = 0;if (p[i].l == l && p[i].r == r){ans = p[i].v;return ans;}push_down(i);ll i1 = i << 1, i2 = i << 1 | 1;if (l <= p[i1].r){if (r <= p[i1].r)ans = ans + query(i1, l, r);elseans = ans + query(i1, l, p[i1].r);}if (r >= p[i2].l){if (l >= p[i2].l){ans = ans + query(i2, l, r);}elseans = ans + query(i2, p[i2].l, r);}return ans;
}ll a[1800000];ll b[1800000];bool vis[1800000];ll d[2500000];map<ll,pair<ll,ll>>q;set<ll>pk;int main()//发现RRR or LLL or RRRLL都是对的，每次只要对应处理区间问题即可{fio();ll t;cin>>t;while(t--){//cout<<66<<endl;q.clear();pk.clear();ll n,m;cin>>n>>m;build(1,1,n);//cout<<66<<endl;for(ll i=1;i<=n;i++)cin>>a[i],b[i]=i,vis[i]=0,d[i]=0;string f;map<ll,ll>ok;cin>>f;ll cnt=0;ll l=0;ll op=0;for(ll i=1;i<=n;i++){if(cnt==0&&a[i]==i)continue;if(a[i]!=i){cnt=max(cnt,a[i]);if(l==0){l=i;}}if(cnt==i){cnt=0;op++;q[op]={l,i};//区间ll o=0;for(ll j=l;j<=i;j++){b[j]=op;vis[j]=1;if(f[j-1]=='R')o++;}ok[op]=o;//pk.insert();l=0;}}//cout<<66<<endl;for(ll i=0;i<f.size();i++){if(f[i]=='L')udq(1,0,0,i+1,i+1);else udq(1,1,0,i+1,i+1);}//cout<<66<<endl;cnt=0;//cout<<op<<endl;for(ll i=1;i<=op;i++){ll c=ok[i];ll l=q[i].first;ll r=q[i].second;//cout<<c<<" "<<r<<" "<<l<<endl;if(c==r-l+1)continue;ll j=(r-l+1)-c;if(query(1,r-j+1,r)==0){continue;}else cnt++;}//cout<<cnt<<endl;while(m--){ll wz;cin>>wz;if(vis[wz]==0){if(cnt==0)cout<<"YES"<<endl;else cout<<"NO"<<endl;}else {if(f[wz-1]=='L'){f[wz-1]='R';ll c=ok[b[wz]];ll l=q[b[wz]].first;ll r=q[b[wz]].second;ll j=(r-l+1)-c;ll hl1=0;if(c==r-l+1||query(1,r-j+1,r)==0){hl1=1;}udq(1,1,0,wz,wz);ok[b[wz]]++;c++;ll hl2=0;j=(r-l+1)-c;if(c==r-l+1||query(1,r-j+1,r)==0){hl2=1;}if(hl1==0&&hl2==1)cnt--;else if(hl1==1&&hl2==0)cnt++;if(cnt==0)cout<<"YES"<<endl;else cout<<"NO"<<endl;}else {f[wz-1]='L';ll c=ok[b[wz]];ll l=q[b[wz]].first;ll r=q[b[wz]].second;ll j=(r-l+1)-c;ll hl1=0;if(c==r-l+1||query(1,r-j+1,r)==0){hl1=1;}udq(1,0,0,wz,wz);ok[b[wz]]--;c--;ll hl2=0;j=(r-l+1)-c;if(c==r-l+1||query(1,r-j+1,r)==0){hl2=1;}if(hl1==0&&hl2==1)cnt--;else if(hl1==1&&hl2==0)cnt++;if(cnt==0)cout<<"YES"<<endl;else cout<<"NO"<<endl;}}}}}
