首页 > 代码库 > 10.23 noip模拟试题
10.23 noip模拟试题
尼玛蛋pdf好难粘
直接写了
T1
/*开始写wa了 我真弱2333 关于p的排序规则不只是差值 为了字典序最小 还要拍别的*/#include<cstdio>#include<algorithm>#define maxn 100010#define inf 1e7#define mem(a,b) for(int i=0;i<=n;i++)a[i]=b[i];using namespace std;int n,m,ans=inf,k;char s[maxn],r[maxn],l[maxn];struct node{ int c,o;}p[maxn];int cmp(const node &x,const node &y){ if(x.c!=y.c)return x.c<y.c;//差值优先 int i=x.o,j=y.o; if(s[i]==s[j]){//相等的特盘 if(s[i]-‘0‘<k)return i>j; else return i<j; } return s[i]>s[j];//优先改数大的 大的大的大的 话说这sort的cmp不能写很多if好像 会慢死 }int Abs(int x){ return x>0?x:-x;}int Cmp(){ for(int i=1;i<=n;i++){ if(l[i]<r[i])return 1; if(l[i]>r[i])return 0; }}int main(){ freopen("number.in","r",stdin); freopen("number.out","w",stdout); scanf("%d%d%s",&n,&m,s+1); for(k=0;k<=9;k++){ for(int i=1;i<=n;i++){ p[i].c=Abs(s[i]-‘0‘-k); p[i].o=i; } sort(p+1,p+1+n,cmp); int mx=0; for(int i=1;i<=m;i++) mx+=p[i].c; if(mx<ans){ ans=mx;mem(r,s); for(int i=1;i<=m;i++) r[p[i].o]=k+‘0‘; } else if(ans==mx){ ans=mx;mem(l,s); for(int i=1;i<=m;i++) l[p[i].o]=k+‘0‘; if(Cmp())mem(r,l); } } printf("%d\n",ans); for(int i=1;i<=n;i++) printf("%c",r[i]); return 0;}
T2
/*1 S=a1 c=a2-a12 S=a1 c=a3-a13 S=a2 c=a3-a2我晕 还带验证合法性 尼玛SP个毛啊 wo de da an dui a */#include<cstdio>#define maxn 200010using namespace std;int n,a[maxn],S,c,A[maxn],B[maxn],cnt;bool f[maxn];int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}void Clear(){ cnt=0; for(int i=0;i<=n;i++) f[i]=A[i]=B[i]=0;}bool Judge(){ int now=a[S]; for(int i=S;i<=n;i++) if(a[i]==now){ f[i]=1;now+=c;B[++B[0]]=a[i]; A[0]=0;int falg=0; for(int j=1;j<=n;j++) if(!f[j])A[++A[0]]=a[j]; if(A[0]<=1||B[0]<=1)continue; int C=A[2]-A[1]; for(int j=3;j<=A[0];j++) if(A[j]-A[j-1]!=C){ falg=1;break; } if(falg==0)return 1; }}void Printf(){ printf("%d ",B[0]); for(int i=1;i<B[0];i++) printf("%d ",B[i]); printf("%d\n",B[B[0]]); printf("%d ",A[0]); for(int i=1;i<A[0];i++) printf("%d ",A[i]); printf("%d\n",A[A[0]]);}int main(){ freopen("progression.in","r",stdin); freopen("progression.out","w",stdout); n=init(); for(int i=1;i<=n;i++) a[i]=init(); S=1;c=a[2]-a[1]; if(Judge()){Printf();return 0;} Clear();S=1;c=a[3]-a[1]; if(Judge()){Printf();return 0;} Clear();S=2;c=a[3]-a[2]; if(Judge()){Printf();return 0;} printf("No solution\n"); return 0;}
T3
/*我尼玛今天刚意识到 这样Dfs是O(m)的啊 啊 啊 很自信地暴力 华丽的T了*/#include<cstdio>#define maxm 10010#define maxn 510using namespace std;int n,m,Q,num,head[maxn],f[maxn],cnt,l,r;struct node{ int o,v,pre;}e[maxm*2];int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}void Add(int from,int to,int x){ num++;e[num].v=to; e[num].o=x; e[num].pre=head[from]; head[from]=num;}void Dfs(int x){ for(int i=head[x];i;i=e[i].pre){//O()O()O()O if((e[i].o>=l&&e[i].o<=r)||f[e[i].v])continue; f[e[i].v]=1;Dfs(e[i].v); }}int main(){ freopen("network5.in","r",stdin); freopen("network.out","w",stdout); n=init();m=init();int u,v; for(int i=1;i<=m;i++){ u=init();v=init(); Add(u,v,i);Add(v,u,i); } Q=init(); while(Q--){ for(int i=1;i<=n;i++)f[i]=0; l=init();r=init();cnt=0; for(int i=1;i<=n;i++) if(f[i]==0){ f[i]=1;cnt++;Dfs(i); } printf("%d\n",cnt); } return 0;}
/*并茶几~边老多老多 有很多很多虚的渣的没用的 因为不能用的是一段区间 所以能用的就是 前缀 后缀预处理统计出有贡献的边们然后Q次询问就成了每次O(n) */#include<cstdio>#define maxm 10010#define maxn 510#define Cf for(int i=0;i<=n;i++)fa[i]=iusing namespace std;int n,m,Q,A[maxm],B[maxm],fa[maxn];struct node{ int u,v;}p[maxm];int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}int find(int x){ if(x!=fa[x])return fa[x]=find(fa[x]); return fa[x];}int main(){ freopen("network.in","r",stdin); freopen("network.out","w",stdout); n=init();m=init();int u,v;Cf; for(int i=1;i<=m;i++){ u=init();v=init(); p[i].u=u;p[i].v=v; } for(int i=1;i<=m;i++){ int r1=find(p[i].u); int r2=find(p[i].v); if(r1!=r2){ fa[r2]=r1;A[++A[0]]=i; } } Cf; for(int i=m;i>=1;i--){ int r1=find(p[i].u); int r2=find(p[i].v); if(r1!=r2){ fa[r2]=r1;B[++B[0]]=i; } } Q=init(); while(Q--){ Cf;int l,r,cnt=0; l=init();r=init(); for(int i=1;i<=A[0];i++){ if(A[i]>=l)break; int r1=find(p[A[i]].u); int r2=find(p[A[i]].v); if(r1!=r2){ fa[r2]=r1;cnt++; } } for(int i=1;i<=B[0];i++){ if(B[i]<=r)break; int r1=find(p[B[i]].u); int r2=find(p[B[i]].v); if(r1!=r2){ fa[r2]=r1;cnt++; } } printf("%d\n",n-cnt); } return 0;}
10.23 noip模拟试题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。