https://codeforces.com/contest/1898
C题可以造一个大小为4的环，然后再造一个来回，这样就解决了%4=0,%4=2的情况，而奇数的情况显然无解。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
#define R printf("%c ",'R')
#define B printf("%c ",'B')
#define BL puts("")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll inf=1ll<<60;
const int N=1e6+5;
ll n,m,k,t;
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
scanf("%lld %lld %lld",&n,&m,&k);
t=(k-n-m+2);
if (t<0 || (t%4)&1) {
puts("NO"); continue;
}
puts("YES");
fo(i,1,n-1) {
fo(j,1,m-1) if (j&1) R; else B;
BL;
}
if (n==3) {
fo(j,1,m-1) if (j&1) R; else B;
BL;
}
else {
fo(j,1,m-1) if ((n+j)&1) B; else R;
BL;
}
B; B; fo(j,3,m) if (j&1) R; else B;
BL;
B; B; fo(j,3,m) if (j&1) B; else R;
BL;
fo(i,3,n-1) {
fo(j,1,m) {
if ((i+j)&1) B; else R;
}
BL;
}
}
return 0;
}
D题显然应该是找两个不相交的区间才能增大。
设li<ri<lj<rj
则答案为2(lj-ri) 那么我们按l从小到大排序，维护最小的r就行。
感觉比c简单。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const int inf=1<<30;
const int N=2e5+5;
struct node{
ll x,y;
};
node a[N];
ll ans,n,mx;
bool cmp(node a,node b){
return a.x<b.x;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
ans=0;
scanf("%lld",&n);
fo(i,1,n) scanf("%lld",&a[i].x);
fo(i,1,n) scanf("%lld",&a[i].y);
fo(i,1,n) {
ans+=abs(a[i].x-a[i].y);
if (a[i].x>a[i].y) swap(a[i].x, a[i].y);
}
mx=0;
sort(a+1,a+n+1,cmp);
ll r=inf;
fo(i,1,n) {
r=min(r, a[i].y);
mx=max(mx, 2ll*max(a[i].x-r,0ll));
}
printf("%lld\n",ans+mx);
}
return 0;
}
E
对于t，假设当前到第i位
我们需要在s中找到一个sj=ti，显然这个j应该越小越好，并假设我们已经s的前l的字符已经全部匹配或者删除。
然后我们考虑我们这个j这个位置对[l+1,j-1]这些字符的影响，对于排在ti之后的显然没有影响，小于ti的需要直接删除。
那么我们维护26个指针即可，记录每个字符当前的位置，检查是否有字符小于当前字符的指针在后面就行。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll inf=1ll<<60;
const int N=1e6+5;
char s[N],t[N];
int p[N],nex[N],n,m,c,r[30];
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
scanf("%d %d",&n,&m);
scanf("%s",s+1);
scanf("%s",t+1);
memset(r,0,sizeof(r));
fo(i,0,25) p[i]=n+1;
fd(i,n,1) {
c=s[i]-'a';
nex[i]=p[c];
p[c]=i;
}
bool flag=1;
fo(i,1,m) {
c=t[i]-'a';
while (p[c]<=r[c] && p[c]!=n+1) {
p[c]=nex[p[c]];
}
if (p[c]==n+1) {
flag=0;
break;
}
else {
fo(i,0,c-1) r[i]=max(r[i], p[c]);
p[c]=nex[p[c]];
}
}
if (flag) A;
else B;
}
return 0;
}
F
首先特判type1，type2，
type3最后一定是剩下两个出口，对于一个点，
d1(i,j)+d2(i,j)+d(i,j)
d1，d2分别表示到两个出口的距离，然后d表示到v的距离，也就是两条路在这之后合并了。
那么bfs即可，每个点只会进入两次。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
//#define A puts("YES")
//#define B puts("NO")
#define A puts("Yes")
#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int inf=1<<30;
const int N=1005;
int n,m,sx,sy,a[N][N],d1[N][N],dis[N][N],f[N][N];
int x,y,xx,yy,z,d;
char s[N];
bool vis[N][N];
int w[4][2]={
1,0,
-1,0,
0,1,
0,-1
};
struct node{
int x,y,z,d;
};
queue<node> q;
bool pd(int x,int y){
return (1<=x && x<=n && 1<=y && y<=m && a[x][y]);
}
bool isborder(int x,int y){
return (x==1 || x==n || y==1 || y==m);
}
void work(int x,int y){
if (!pd(x,y)) return;
f[x][y]=(x-1)*n+y;
q.push((node){x,y,(x-1)*n+y});
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
int sum=0;
scanf("%d %d",&n,&m);
fo(i,1,n){
scanf("%s",s+1);
fo(j,1,m) {
if (s[j]=='#') a[i][j]=0;
else a[i][j]=1,sum++;
if (s[j]=='V') {
sx=i; sy=j;
}
}
}
while (!q.empty()) q.pop();
fo(i,1,n) fo(j,1,m) {
vis[i][j]=0;
d1[i][j]=inf;
}
vis[sx][sy]=1;
d1[sx][sy]=0;
q.push((node){sx,sy});
int cnt=0,dm=inf;
if (isborder(sx,sy)) {
cnt++;
dm=0;
}
while (!q.empty()) {
x=q.front().x;
y=q.front().y;
q.pop();
fo(i,0,3){
xx=x+w[i][0];
yy=y+w[i][1];
if (!pd(xx,yy) || vis[xx][yy]) continue;
d1[xx][yy]=d1[x][y]+1;
if (isborder(xx,yy)) {
cnt++;
dm=min(dm,d1[xx][yy]);
}
vis[xx][yy]=1;
q.push((node){xx,yy});
}
}
if (!cnt) {
printf("%d\n",sum-1);
continue;
}
if (cnt==1) {
printf("%d\n",sum-dm-1);
continue;
}
fo(i,1,n) fo(j,1,m) {
vis[i][j]=0;
f[i][j]=dis[i][j]=0;
}
fo(i,1,m) {
work(1,i);
work(n,i);
}
fo(i,1,n) {
work(i,1);
work(i,m);
}
while (!q.empty()) {
x=q.front().x; y=q.front().y; z=q.front().z; d=q.front().d;
q.pop();
fo(i,0,3) {
xx=x+w[i][0];
yy=y+w[i][1];
if (!pd(xx,yy) || vis[xx][yy]) continue;
if (!f[xx][yy]) {
f[xx][yy]=z;
dis[xx][yy]=d+1;
q.push((node){xx,yy,z,d+1});
}
else {
if (f[xx][yy]!=z) {
f[xx][yy]=z;
dis[xx][yy]+=d+1;
vis[xx][yy]=1;
q.push((node){xx,yy,z,d+1});
}
}
}
}
int ans=0;
fo(i,1,n) fo(j,1,m) {
if (d1[i][j]!=inf) {
ans=max(ans, sum-dis[i][j]-d1[i][j]-1);
if (dis[i][j]+d1[i][j]==0) printf("%d %d\n",i,j);
}
}
printf("%d\n",ans);
}
return 0;
}