厦门网站建设优化,宿迁做企业网站,建网站服务商,为什么做的网站搜不出来交题#xff1a;https://cms.ioi-jp.org/documentation
A
给一个序列 a1,⋯,ana_1,\cdots,a_na1,⋯,an。 执行nnn个操作#xff0c;第iii个操作为找出第iii个数前离其最近且与它相同的数的位置#xff0c;把这两个数之间的数全部赋值aia_iai。求最后的序列。
考虑第…交题https://cms.ioi-jp.org/documentation
A
给一个序列 a1,⋯,ana_1,\cdots,a_na1,⋯,an。 执行nnn个操作第iii个操作为找出第iii个数前离其最近且与它相同的数的位置把这两个数之间的数全部赋值aia_iai。求最后的序列。
考虑第iii个操作执行完后iii之前每个数一定是连续出现正好一段或不出现。
#includebits/stdc.h
using namespace std;
#define For(i,n) for(int i1;in;i)
#define Fork(i,k,n) for(int ik;in;i)
#define ForkD(i,k,n) for(int in;ik;i--)
#define Rep(i,n) for(int i0;in;i)
#define ForD(i,n) for(int in;i;i--)
#define RepD(i,n) for(int in;i0;i--)
#define Forp(x) for(int ppre[x];p;pnext[p])
#define Forpiter(x) for(int piter[x];p;pnext[p])
#define Lson (o1)
#define Rson ((o1)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 vectorint
#define pi pairint,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) couta[i] ; couta[n]endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) couta[i][j] ;\couta[i][m]endl; \}
#pragma comment(linker, /STACK:102400000,102400000)
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) amax(a,b);
#define gmin(a,b) amin(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 (ab)%F;}
ll sub(ll a,ll b){return ((a-b)%FF)%F;}
void upd(ll a,ll b){a(a%Fb%F)%F;}
inline int read()
{int x0,f1; char chgetchar();while(!isdigit(ch)) {if (ch-) f-1; chgetchar();}while(isdigit(ch)) { xx*10ch-0; chgetchar();}return x*f;
}
int a[201000];
mapint,pairint,int h;
int main()
{
// freopen(A.in,r,stdin);
// freopen(.out,w,stdout);int nread();For(i,n) a[i]read(); stack pairpairint,int , int st;For(i,n) {if(st.empty() || !h.count(a[i]) || h[a[i]] mp(0,0) ) {st.push(mp(mp(i,i),a[i]));h[a[i]]mp(i,i);}else {while(!st.empty()) {auto pst.top();st.pop();if(p.sea[i]) {h[p.se]mp(p.fi.fi,i);st.push(mp(h[p.se],a[i]));break;}else {h[p.se]mp(0,0);}}}}while(!st.empty()) {auto pst.top();st.pop();Fork(i,p.fi.fi,p.fi.se) a[i]p.se;}For(i,n) couta[i]endl;return 0;
}
B
给nnn个点对每个点对(x,y)(x,y)(x,y)可以覆盖S(a,b)∣by,∣a−x∣y−bS{(a,b)|by,|a-x|y-b}S(a,b)∣by,∣a−x∣y−b。问取多少个点对能覆盖所有点对。
经典题
#includebits/stdc.h
using namespace std;
#define For(i,n) for(int i1;in;i)
#define Fork(i,k,n) for(int ik;in;i)
#define ForkD(i,k,n) for(int in;ik;i--)
#define Rep(i,n) for(int i0;in;i)
#define ForD(i,n) for(int in;i;i--)
#define RepD(i,n) for(int in;i0;i--)
#define Forp(x) for(int ppre[x];p;pnext[p])
#define Forpiter(x) for(int piter[x];p;pnext[p])
#define Lson (o1)
#define Rson ((o1)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 vectorint
#define pi pairint,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) couta[i] ; couta[n]endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) couta[i][j] ;\couta[i][m]endl; \}
#pragma comment(linker, /STACK:102400000,102400000)
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) amax(a,b);
#define gmin(a,b) amin(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 (ab)%F;}
ll sub(ll a,ll b){return ((a-b)%FF)%F;}
void upd(ll a,ll b){a(a%Fb%F)%F;}
inline int read()
{int x0,f1; char chgetchar();while(!isdigit(ch)) {if (ch-) f-1; chgetchar();}while(isdigit(ch)) { xx*10ch-0; chgetchar();}return x*f;
}
int n;
vectorpairint,int v;
int main()
{
// freopen(B.in,r,stdin);
// freopen(.out,w,stdout);int nread();For(i,n) {int aread(),bread();v.pb(mp(b-a,ab));}sort(ALL(v));stackpairint,int st; for(int i0;in;i) {auto nowv[i];while(!st.empty()){auto tst.top();if(t.finow.fi t.se now.se) {st.pop(); }else break;}st.push(now);}coutSI(st)endl;return 0;
}
C
考虑n*n的四连通矩阵每次可以上下左右走一个。 格子上有颜色黑、白且只有白色能走。现在你希望令2个白色格子连通。一次操作为把n∗nn*nn∗n的矩阵赋值为白色。问至少几次操作实现目标。
#includebits/stdc.h
using namespace std;
#define For(i,n) for(int i1;in;i)
#define Fork(i,k,n) for(int ik;in;i)
#define ForkD(i,k,n) for(int in;ik;i--)
#define Rep(i,n) for(int i0;in;i)
#define ForD(i,n) for(int in;i;i--)
#define RepD(i,n) for(int in;i0;i--)
#define Forp(x) for(int ppre[x];p;pnext[p])
#define Forpiter(x) for(int piter[x];p;pnext[p])
#define Lson (o1)
#define Rson ((o1)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 vectorint
#define pi pairint,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) couta[i] ; couta[n]endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) couta[i][j] ;\couta[i][m]endl; \}
#pragma comment(linker, /STACK:102400000,102400000)
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) amax(a,b);
#define gmin(a,b) amin(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 (ab)%F;}
ll sub(ll a,ll b){return ((a-b)%FF)%F;}
void upd(ll a,ll b){a(a%Fb%F)%F;}
inline int read()
{int x0,f1; char chgetchar();while(!isdigit(ch)) {if (ch-) f-1; chgetchar();}while(isdigit(ch)) { xx*10ch-0; chgetchar();}return x*f;
}
int r,c,n,sx,sy,tx,ty;
int dir[4][2]{{1,0},{-1,0},{0,1},{0,-1}};
bool inside(int x,int y) {return 1x xr 1y yc;
}
vectorstring a;
bool state(int x,int y){return a[x-1][y-1]#;
}
pairint,int dis[600000010];
int id(int x,int y) {return c*(x-1)y;
}
void pri(pairint,int p) {printf((%d,%d),p.fi,p.se);
}
void pri(vectorpairint,int v) {for(auto a:v) {pri(a);cout:;int xa.fi,ya.se;pri(dis[id(x,y)]);cout ;}coutendl;
}
void bfs() {vectorpairint,int q0,qa,qb;int nowdis0;For(i,r*c) dis[i]mp(INF,INF);dis[id(sx,sy)]mp(0,n);q0.pb(mp(sx,sy));while(SI(q0)) {int nxdisnowdis1;// relax q0for(int i0;iSI(q0);i) {auto tq0[i];int xt.fi,yt.se;auto now_disdis[id(x,y)];Rep(di,4) {int nxxdir[di][0],nyydir[di][1];if(!inside(nx,ny)) continue;if(dis[id(nx,ny)]!mp(INF,INF)) continue;int stastate(nx,ny);if(sta0) { //whitedis[id(nx,ny)] now_dis;q0.pb(mp(nx,ny));}}} // q0 - qaRep(i,SI(q0)) {qa.pb(q0[i]);}Rep(i,SI(qa)) {auto tqa[i];int xt.fi,yt.se;auto now_disdis[id(x,y)];Rep(di,2) {int nxxdir[di][0],nyydir[di][1];if(!inside(nx,ny)) continue;if(dis[id(nx,ny)]!mp(INF,INF)) continue;int stastate(nx,ny);if(now_dis.finowdis) {dis[id(nx,ny)] mp(nxdis,1);}else if(now_dis.se1n){dis[id(nx,ny)] mp(nxdis,now_dis.se1);}else continue;qa.pb(mp(nx,ny));}}//qa - abRep(i,SI(qa)) {qb.pb(qa[i]);}Rep(i,SI(qb)) {auto tqb[i];int xt.fi,yt.se;auto now_disdis[id(x,y)];Fork(di,2,3) {int nxxdir[di][0],nyydir[di][1];if(!inside(nx,ny)) continue;if(dis[id(nx,ny)]!mp(INF,INF)) continue;int stastate(nx,ny);if(now_dis.finowdis) {dis[id(nx,ny)]mp(nxdis,n1);}else if(now_dis.finxdis now_dis.sen n12*n ) {dis[id(nx,ny)]mp(nxdis,n1);}else if(now_dis.finxdis now_dis.sen n22*n ) {dis[id(nx,ny)]mp(nxdis,n2);}else if(now_dis.finxdis now_dis.sen now_dis.se12*n ) {dis[id(nx,ny)]mp(nxdis,now_dis.se1);}else continue;qb.pb(mp(nx,ny));}}
//
// coutnowdisendl;
// coutq0endl;
// pri(q0);
// coutqaendl;
// pri(qa);
// coutqbendl;
// pri(qb);
// //ab - qc(q0)q0.resize(0);for(int i0;iqb.size();i) {auto tqb[i];int xt.fi,yt.se;auto now_disdis[id(x,y)];if(now_dis.finxdis)q0.pb(qb[i]);}qa.resize(0),qb.resize(0);nowdis;}
// For(i,r) {
// For(j,c) pri(dis[id(i,j)]),putchar( );
// puts();
// }coutdis[id(tx,ty)].fiendl;}
int main()
{
// freopen(C.in,r,stdin);
// freopen(.out,w,stdout);cinrcn;
// For(i,r) For(j,c) coutid(i,j) ;cinsxsytxty;For(i,r) {string s;cins;a.pb(s);}bfs();return 0;
}
D Cat Exercise
给一个nnn个节点的树点权aia_iai。 执行如下操作
选取点权最大的点删除这个点及其相连的边若有剩余连通块中取一个跳回1。否则结束。
问操作1取的点权的和最大值。
