A
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
int a=0, f=1; char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) a=a*10+c-'0', c=getchar();
return a*f;
}
map<string,string> mp;
signed main() {
mp["red"]="SSS";
mp["blue"]="FFF";
mp["green"]="MMM";
string s;
cin>>s;
if(mp.count(s)) cout<<mp[s]<<endl;
else cout<<"Unknown"<<endl;
return 0;
}B
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
int a=0, f=1; char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) a=a*10+c-'0', c=getchar();
return a*f;
}
int n;
priority_queue<int,vector<int>,greater<int> > q;
signed main() {
n=read();
while(n--) {
int op=read();
if(op==1) {
int x=read();
q.push(x);
} else {
int x=q.top(); q.pop();
cout<<x<<endl;
}
}
return 0;
}C
没做出来捏。
D
维护一个 01 串的区间反转，单点查询。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
int a=0, f=1; char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) a=a*10+c-'0', c=getchar();
return a*f;
}
const int N=5e5+5;
int n, m;
string s[2];
namespace BIT {
int c[N];
int lowbit(int x) { return x&-x; }
void add(int x) {
for(;x<=n;x+=lowbit(x)) c[x]^=1;
}
int query(int x) {
int y=0;
for(;x;x-=lowbit(x)) y^=c[x];
return y;
}
}
signed main() {
n=read(), m=read();
cin>>s[0];
cin>>s[1];
s[0]=" "+s[0];
s[1]=" "+s[1];
while(m--) {
int l=read(), r=read();
BIT::add(l);
BIT::add(r+1);
}
rep(i,1,n) {
int t=BIT::query(i);
cout<<s[t][i];
}
cout<<endl;
return 0;
}E
题目中的条件转化一下就是
- $m \mid\sum_{i=1}^l A_i$
- $\forall i \in [1,n-l]$，$m \mid A_{i+l}-A_i$。由数论知识显然。更进一步地，$A_i \equiv A_{i+l} \pmod {m}$。我们称同余的这个数 $j$ 为这组的特征元素。
不难发现这是充要的。考虑滑动窗口的变化。
于是每个 $A_{i},A_{i+l},A_{i+2l} ,\ldots$ 就相对独立了，可以分开考虑。
设 $f(i,j)$ 表示考虑 $[1,i]$，其中前 $i$ 组的特征元素的和模 $m$ 为 $j$ 时，需要的最小代价。
转移枚举当前组的特征元素 $j \in [0,m)$，贪心修改每个元素。然后枚举 $k$，用 $f(i-1,j)$ 更新 $f\left(i,\left(j+k\right) \bmod m\right)$ 即可。
复杂度 $O(nm^2)$。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
int a=0, f=1; char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) a=a*10+c-'0', c=getchar();
return a*f;
}
const int N=505;
int n, m, l, a[N], s[N], f[N][N];
signed main() {
n=read(), m=read(), l=read();
rep(i,1,n) {
a[i]=read();
s[i]=s[i-1]+a[i];
}
rep(i,0,n) rep(j,0,m) f[i][j]=1e9;
f[0][0]=0;
rep(i,1,l) rep(j,0,m-1) {
int res=0;
for(int k=i;k<=n;k+=l) {
if(j>=a[k]) res+=j-a[k]; else res+=j-a[k]+m;
}
rep(k,0,m-1) f[i][(k+j)%m]=min(f[i][(k+j)%m],f[i-1][k]+res);
}
cout<<f[l][0]<<endl;
return 0;
}F
又是动态 DP？