题面
\(1143A\)
咕咕
n=read();
fp(i,1,n)a[i]=read(),++cnt[a[i]];
fp(i,1,n)if(++c[a[i]]==cnt[a[i]])return printf("%d\n",i),0;
\(1143B\)
显然最终的答案肯定是后面一堆\(9\)加上前面的数字，模拟一下就行了
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
int n,tmp,res,mx,now;
inline int calc(R int x){int res=1;while(x)res*=x%10,x/=10;return res;}
int main(){
// freopen("testdata.in","r",stdin);
scanf("%d",&n);
mx=calc(n),res=n;
for(int i=1;res/10;i*=10){
tmp+=res%10*i,res/=10;
now+=9*i;
cmax(mx,calc((tmp>=now?res:res-1)*i*10+now));
}
printf("%d\n",mx);
return 0;
}
\(1143C\)
显然合法的点永远合法，不合法的点永远不合法，直接把所有合法的点找出来\(sort\)一下就行了
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]=' ';
}
const int N=1e5+5;
struct eg{int v,nx;}e[N<<1];int head[N],tot;
inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}
int sz[N],val[N],vva[N],st[N];
int n,rt,top,x;
void dfs(int u){
sz[u]=1,vva[u]=val[u];
go(u)dfs(v),++sz[u],vva[u]+=val[v];
if(sz[u]==vva[u])st[++top]=u;
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();
fp(i,1,n){
x=read(),val[i]=read();
if(~x)add(x,i);else rt=i;
}
dfs(rt);
sort(st+1,st+1+top);
if(!top)return puts("-1"),0;
else fp(i,1,top)print(st[i]);
return Ot(),0;
}
\(1142A\)
首先如果环长为\(p\)，跨一步距离为\(a\)，那么\({p\over \gcd(p,a)}\)步之后可以回到原点
所以枚举一下开头和第一次跳到的地方就行了，开头只有两个是有用的
//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
int n,k,a,b,s,t;ll mx,mn,p,res;
ll calc(R ll x,R ll y){R ll k=(y-x+p)%p;return p/__gcd(p,k);}
int main(){
// freopen("testdata.in","r",stdin);
scanf("%d%d%d%d",&n,&k,&a,&b),mx=0,mn=1e18,p=1ll*n*k;
s=a+1;
for(t=b+1;t<=p;t+=k)res=calc(s,t),cmax(mx,res),cmin(mn,res);
for(t=k+1-b;t<=p;t+=k)res=calc(s,t),cmax(mx,res),cmin(mn,res);
s=k+1-a;
for(t=b+1;t<=p;t+=k)res=calc(s,t),cmax(mx,res),cmin(mn,res);
for(t=k+1-b;t<=p;t+=k)res=calc(s,t),cmax(mx,res),cmin(mn,res);
printf("%I64d %I64d\n",mn,mx);
return 0;
}
\(1142B\)
因为是这个排列的循环位移，所以每一个数前面能接哪个数是已经确定的了，记为\(las\)
对于\(a\)中的每一个数字，显然是接在前面离它最近的值为\(las\)的数后面最优，对于每一个数都预处理出它应该接在谁后面，记为\(to[i]\)
显然，对于\(i\)来说，它跳\(n-1\)次\(to[i]\)之后到达的点是一个合法的点，且是最右边的合法的点。我们可以倍增预处理出对于每一个点\(i\)最右边的合法的点，记为\(pos_i\)
那么就是有一堆区间\([pos_i,i]\)，以及一对询问\([l,r]\)，每次问你有多少区间被询问区间完全包含
我们离线，把询问按右端点排序，每次对于一个点\(i\)，把它的左端点，也就是\(pos_i\)加入一个树状数组，那么对于所有右端点为\(i\)的询问来说，显然只有现在在树状数组中的，且位置在\([l,r]\)之间的左端点是有用的，查询一下就行了
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int K=-1,Z=0;
inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}
const int N=2e5+5;
struct node{
int l,r,id;
inline bool operator <(const node &b)const{return r<b.r;}
}q[N];
int n,m,Q,k;
int c[N],a[N],b[N],las[N],to[N][25],pos[N],p[N],ans[N];
inline void upd(R int x){for(;x<=m;x+=x&-x)++c[x];}
inline int qwq(R int x){int res=0;for(;x;x-=x&-x)res+=c[x];return res;}
inline int query(R int l,R int r){return qwq(r)-qwq(l-1);}
void init(){
fp(j,1,20)fp(i,(1<<j)+1,m)to[i][j]=to[to[i][j-1]][j-1];
k=n-1;
fp(i,n,m){
int x=i;
fd(j,20,0)if(k>>j&1)x=to[x][j];
p[i]=x;
}
}
int main(){
// freopen("testdata.in","r",stdin);
n=read(),m=read(),Q=read();
fp(i,1,n)a[i]=read(),las[a[i]]=a[i-1];
las[a[1]]=a[n];
fp(i,1,m)b[i]=read(),to[i][0]=pos[las[b[i]]],pos[b[i]]=i;
init();
fp(i,1,Q)q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+1+Q);
for(R int i=1,j=1;i<=m;++i){
if(p[i])upd(p[i]);
while(j<=Q&&q[j].r==i)ans[q[j].id]=query(q[j].l,i),++j;
}
fp(i,1,Q)sr[++K]=(ans[i]?'1':'0');sr[++K]='\n';
return Ot(),0;
}
\(1142C\)
我sb了这都没想到……
假设有一个点满足\(y>x^2+bx+c\)，那么就是有\(y-x^2>bx+c\)
所以我们把每个点的坐标转化为\((x,y-x^2)\)，那么就可以转化为不在直线的上方，直接求个上凸包，计算一下凸包上的边数就可以了
//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define inf 0x3f3f3f3f
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
const int N=1e5+5;
struct node{
ll x,y;
inline node(){}
inline node(R ll xx,R ll yy):x(xx),y(yy){}
inline node operator +(const node &b)const{return node(x+b.x,y+b.y);}
inline node operator -(const node &b)const{return node(x-b.x,y-b.y);}
inline ll operator *(const node &b)const{return x*b.y-y*b.x;}
inline bool operator <(const node &b)const{return x==b.x?y>b.y:x<b.x;}
}p[N],st[N];
int n,top;
void solve(){
sort(p+1,p+1+n),p[0].x=inf;
fp(i,1,n)if(p[i].x!=p[i-1].x){
while(top>1&&(st[top]-st[top-1])*(p[i]-st[top-1])>=0)--top;
st[++top]=p[i];
}
printf("%d\n",top-1);
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();
for(R int i=1,x,y;i<=n;++i)x=read(),y=read(),p[i]=node(x,y-1ll*x*x);
solve();
return 0;
}
\(1142D\)
话说巨巨们写完题就不能顺手写个题解么……对着\(yyb\)巨巨那长达\(20\)行的代码盯了一个下午……
首先题目里说的太麻烦了，我们把它用代码的形式写出来，大概是这样的
fp(i,1,9)q[++t]=i;
while(true){
int u=q[h];
fp(j,0,h%11-1)q[++t]=q[h]*10+j;
++h;
}
那么我们发现这个数列显然是递增的
我们先来思考一个问题，对于数列中的第\(i\)个数，往它后面怼一个\(c\)，那么这个新的数在数列中的标号是多少呢？
因为这个数列是递增的，那么显然我们只需要计算出有多少数比它小就可以了
先给出柿子，\(i\)后面怼一个\(c\)，新的数的标号为
\[9+\sum_{k=1}^{i-1}k\%11+c+1
\]
\]
\(9\)代表初始的\(9\)个数，然后\(1\)到\(i-1\)中每个数后面怼一个数位显然都会比新数小，\(c+1\)应该不用解释了
然而这柿子看着就很麻烦……我们发现后面可以怼的数字只与标号对\(11\)取模的值有关，我们尝试把整个柿子都放到\(\bmod 11\)的意义下，这样就能把中间的\(k\%11\)去掉了
\[9+\sum_{k=1}^{i-1}k+c+1\bmod 11
\]
\]
\[9+{i(i-1)\over 2}+c+1\bmod 11
\]
\]
如此这般之后，我们发现数字的标号，其实只需要维护\(\bmod 11\)意义下的值就可以了
我们设\(f_{i,j}\)表示末尾数位为\(s[i]\)，标号在\(\bmod 11\)意义下为\(j\)，且能匹配上以\(i\)为结尾的子串的数的个数
我们记上面那个值为\(nxt(i,j)\)，就是标号为\(i\)的后面怼个\(j\)的数的标号，那么转移就有
\[f_{i,nxt(j,s[i])}+=f_{i-1,j}
\]
\]
记得这里要满足\(j>s[i]\)
顺便注意如果\(s[i]>0\)的话单独一个数字也是可以匹配的
//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(char *s){
R int len=0;R char ch;while(((ch=getc())>'9'||ch<'0'));
for(s[++len]=ch;(ch=getc())>='0'&&ch<='9';s[++len]=ch);
return s[len+1]='\0',len;
}
const int N=1e5+5;
char s[N];int f[N][15],n;ll res;
inline int nxt(R int x,R int c){return ((x*(x-1)>>1)+c+10)%11;}
int main(){
// freopen("testdata.in","r",stdin);
n=read(s);
fp(i,1,n){
fp(j,s[i]-'0'+1,10)f[i][nxt(j,s[i]-'0')]+=f[i-1][j];
if(s[i]>'0')++f[i][s[i]-'0'];
fp(j,0,10)res+=f[i][j];
}
printf("%I64d\n",res);
return 0;
}
\(1142E\)
好迷……
我们先考虑完全没有粉色边的情况
我们维护一个\(top\)集合，集合里是所有可能成为答案的点，并且维护一个\(gg\)集合，里面是所有不可能成为答案的点（严格来说还是有可能成为答案的，只不过我们不需要了）
然后我们每次从\(top\)集合里取出两个点，询问它们之间的边的方向，如果边形如\((u,v)\)，就把\(v\)从\(top\)集合里取出，加入\(gg\)集合
那么最后\(top\)集合里只剩一个点的时候这个点显然可以成为答案
然而粉色边的参战导致事情变得辣手了起来
大体思路还是和之前一样的，只不过我们一开始并不能把所有点都加入\(top\)集合里不然跟一开始的情况有什么区别……
我们先把所有的粉边构成的强连通分量搞出来，然后每个强连通分量里取出一个点加入\(top\)集合
然后照例每次从\(top\)集合里取出两个点，假设边的方向为\((u,v)\)，那么照例把\(v\)删掉就万事大吉……
等会儿\((u,v)\)是绿色的吧？\(v\)到它所在强连通分量中的点的边是粉色的吧？这显然颜色不同啊？
也就是说，只有\(v\)是需要加入\(gg\)集合的，而\(v\)所在的强连通分量中其它的点可能还是需要加入\(top\)集合的
那么我们把每个强连通分量删掉一些边使之成为一个\(DAG\)，每次把度数为\(0\)的点加入\(top\)集合，然后询问完之后把\(v\)以及\(v\)连出去的所有边都删掉，再看看有没有度数为\(0\)的点就是了，需不需要加入\(top\)就是了。直到\(top\)集合只剩下一个元素为止
正确性？显然所有\(gg\)集合里的元素都能通过绿色边走到，既不在\(top\)也不在\(gg\)里的元素都可以通过粉色边到达，那么正确性就没问题了
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
int read(){
R int res,f=1;R char ch;
while((ch=getchar())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getchar())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
inline int get(){R char ch;while((ch=getchar())>'1'||ch<'0');return ch-'0';}
const int N=1e5+5;
struct eg{int v,nx;}e[N<<1];int head[N],tot;
inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}
inline bool query(R int u,R int v){printf("? %d %d\n",u,v),fflush(stdout);return read();}
int vis[N],ins[N],deg[N];vector<int>to[N],now;
int n,m;
void tarjan(int u){
vis[u]=ins[u]=1;
go(u){
if(!ins[v])to[u].push_back(v),++deg[v];
if(!vis[v])tarjan(v);
}
ins[u]=0;
}
int main(){
n=read(),m=read();
for(R int i=1,u,v;i<=m;++i)u=read(),v=read(),add(u,v);
fp(i,1,n)if(!vis[i])tarjan(i);
fp(i,1,n)if(!deg[i])now.push_back(i);
while(now.size()>1){
int u=now.back();now.pop_back();
int v=now.back();now.pop_back();
if(!query(u,v))swap(u,v);now.push_back(u);
fp(i,0,to[v].size()-1)if(!--deg[to[v][i]])now.push_back(to[v][i]);
}
printf("! %d\n",now.front());
return 0;
}