# 2018多校联合训练3

xiaoxiao2021-03-01  21

http://acm.hdu.edu.cn/contests/contest_show.php?cid=804

1004：水题，只有2，3，4，6不可以 solved by lyy

#include <bits/stdc++.h> using namespace std; #define ll long long int t,k; int main() { scanf("%d",&t); while (t--) { scanf("%d",&k); if (k==1) printf("5\n"); else if (k==2) printf("7\n"); else printf("%d\n",5+k); } return 0; }

1006：异或和位0是平局，其余都是Q神获胜 solved by lyy

#include <bits/stdc++.h> using namespace std; #define ll long long int t; int n; int main() { scanf("%d",&t); while (t--) { scanf("%d",&n); int ans=0; for (int i=1;i<=n;i++) { int x; scanf("%d",&x); ans^=x; } for (int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); } if (ans==0) printf("D\n"); else printf("Q\n"); } return 0; }

1012：简单模拟题 solved by sdn

/* ID: oodt PROG: LANG:C++ */ #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<string> #include<cstring> #include<cassert> #include<map> #include<vector> #include<queue> #include<stack> #include<set> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} const int maxx=10005; const int INF = 0x3f3f3f3f; int n,m,k; char aa[maxx][maxx]; int vis[maxx]; int ans = 0,cnt = 0,pos = 0; int l = 0,r = 0; int main() { #ifdef LOCAL // freopen("","r",stdin); #endif int T; scanf("%d",&T); while(T--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); int t1 = 2*b; rep(i,0,b*2+1+c*2+1){ rep(j,0,b*2+1+a*2+1){ aa[i][j] = '.'; } } rep(i,0,b*2+1+c*2){ rep(j,a*2,a*2+b*2+1){ if(i % 2){ if(j % 2 == 0){ aa[i][j] = '|'; } else{ aa[i][j] = '/'; } } else if(j%2== 0)aa[i][j] = '+'; } } rep(i,0,b) rep(j,t1-i*2,t1+a*2+1) { if(j % 2 == 0) aa[i*2][j] = '+'; else { aa[i*2][j] = '-'; } } rep(i,0,b) rep(j,t1-i*2-1,t1+a*2+1) { if(j % 2 == 1) aa[i*2+1][j] = '/'; } cnt = 0; for(int i = 0; i < b*2; i++) { for(int j = 0; j < b*2-cnt; j++){ aa[i][j] = '.'; } cnt++; } rep(i,b*2,b*2+c*2+1){ rep(j,0,a*2) { if(i % 2 == 0){ if(j%2 == 0)aa[i][j] = '+'; else aa[i][j] = '-'; } else { if(j%2 == 0) aa[i][j] = '|'; else aa[i][j] = '.'; } } } cnt = 0; for(int i = c*2+b*2; i >= c*2+1; i--) { for(int j = a*2+b*2; j >= a*2+1+cnt; j--){ aa[i][j] = '.'; } cnt++; } for (int i=1;i<=b;i++) { for (int j=2*a+2*b-i*2;j>=0;j--) { if (aa[2*i-1][j+1]=='/') aa[2*i-1][j]='.'; } } for (int j=1;j<=b;j++) { for (int i=2*j;i<=2*b+2*c;i++) { if (aa[i-1][2*a+2*b+1-2*j]=='/') aa[i][2*a+2*b+1-2*j]='.'; } } rep(i,0,b*2+1+c*2){ rep(j,0,b*2+1+a*2){ printf("%c",aa[i][j]); } printf("\n"); } } return 0; }

1001：从左往右递推更新

#include <bits/stdc++.h> using namespace std; #define ll long long int t; int n,m,k,p,q,r; int mod; int a[10000005]; int b[10000005]; int main() { //freopen("in.txt","r",stdin); scanf("%d",&t); while (t--) { scanf("%d%d%d%d%d%d%d",&n,&m,&k,&p,&q,&r,&mod); for (int i=1;i<=k;i++) { scanf("%d",&a[i]); } for (int i=k+1;i<=n;i++) { a[i]=(int)(((ll)p*a[i-1]+(ll)q*i+r)%mod); } //memset(b,0,sizeof(b)); b[n]=n; for (int i=n-1;i>=1;i--) { int x=i+1; while (!(a[x]>a[i] || b[x]==x)) { x=b[x]; } if (a[x]>a[i]) b[i]=x; else b[i]=i; } ll ans_count=0,ans_rate=0; int rate=0; int count=0; for (int i=1;i<=m;i++) { if (a[i]>rate) { rate=a[i]; count++; } } //cout<<"1 "<<rate<<' '<<count<<endl; ans_count+=count^1; ans_rate+=rate^1; for (int i=2;i<=n-m+1;i++) { if (a[i]==a[i-1]) { count=count+(a[i+m-1]>rate); rate=max(rate,a[i+m-1]); } else if (a[i]>a[i-1]) { if (a[i-1]==0) count++; count=count-1+(a[i+m-1]>rate); rate=max(rate,a[i+m-1]); } else { if (b[i-1]==i-1 || b[i-1]>i+m-1) { count=0; rate=0; if (a[i]!=0) { count++; rate=a[i]; } int x=i; while (b[x]!=x && b[x]<=i+m-1) { x=b[x]; count++; rate=a[x]; } } else { if (a[i+m-1]>rate) count++; rate=max(rate,a[i+m-1]); if (a[i]==0) count--; int x=i; while (b[x]!=b[i-1]) { x=b[x]; count++; } count=count+(a[i+m-1]>rate); } } ans_count+=count^i; ans_rate+=rate^i; //cout<<i<<' '<<rate<<' '<<count<<endl; } printf("%lld %lld\n",ans_rate,ans_count); } return 0; }