比賽記錄
注意隨機數據 ,1-n排列這種,一般都有啥暴力重構之類的方法,期望重構次數很少之類的
1005也是這樣,因為n^2但只有n個值有數,所以就可以n^2logn
題解
1001?Salty Fish
unsolved.
1002?Nonsense Time?
?https://blog.csdn.net/liufengwei1/article/details/98785302
杭電卓越班新生考試考什么、代碼:
#include<bits/stdc++.h> #define maxl 50010 using namespace std;int n,mxid,mxval; int a[maxl],kk[maxl],dy[maxl],ans[maxl]; int b[maxl],dp[maxl],frm[maxl]; bool in[maxl],froz[maxl];inline void prework() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),dy[a[i]]=i;for(int i=1;i<=n;i++)scanf("%d",&kk[i]),froz[i]=false; }inline void upd(int i,int x) {while(i<=n){if(dp[b[i]]<dp[x])b[i]=x;i+=i&-i;} }inline int qry(int i) {int res=0;while(i){if(dp[res]<dp[b[i]])res=b[i];i-=i&-i;}return res; }inline void lis() {for(int i=1;i<=n;i++)in[i]=false,frm[i]=0,b[i]=0,dp[i]=0;int id;mxval=0;mxid=0;for(int i=1;i<=n;i++)if(!froz[i]){id=qry(a[i]);dp[i]=dp[id]+1;frm[i]=id;if(dp[i]>mxval)mxval=dp[i],mxid=i;upd(a[i],i);}int u=mxid;while(u!=0)in[u]=true,u=frm[u]; }inline void mainwork() {lis();for(int i=n;i>=1;i--){ans[i]=mxval;froz[kk[i]]=true;if(in[kk[i]])lis();} }inline void print() {for(int i=1;i<=n;i++)printf("%d%c",ans[i],(i==n)?'\n':' '); }int main() {int t;scanf("%d",&t);for(int i=1;i<=t;i++){prework();mainwork();print();}return 0; }
?
1003?Milk Candy
unsolved.
?1004?Speed Dog
unsolved.
1005?Snowy Smile
2020杭電校歷??https://blog.csdn.net/liufengwei1/article/details/98762357
代碼:
#include<bits/stdc++.h> #define maxl 2010 using namespace std;int n,totx,toty; int ax[maxl],ay[maxl],w[maxl]; long long ans; long long a[maxl]; int numx[maxl],numy[maxl]; struct node {int l,r;long long sum,lrmx;long long rmx,lmx; }tree[maxl*4]; vector <int> tmpy[maxl];inline void prework() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&ax[i],&ay[i],&w[i]);numx[i]=ax[i];numy[i]=ay[i];}sort(numx+1,numx+1+n);totx=unique(numx+1,numx+1+n)-numx-1;for(int i=1;i<=totx;i++)tmpy[i].clear();for(int i=1;i<=n;i++){ ax[i]=lower_bound(numx+1,numx+1+totx,ax[i])-numx;tmpy[ax[i]].push_back(i);}sort(numy+1,numy+1+n);toty=unique(numy+1,numy+1+n)-numy-1;for(int i=1;i<=n;i++)ay[i]=lower_bound(numy+1,numy+1+toty,ay[i])-numy; }inline void pushup(int k) {int ls=k<<1,rs=k<<1|1;tree[k].sum=tree[ls].sum+tree[rs].sum;tree[k].lrmx=max(tree[ls].lrmx,tree[rs].lrmx);tree[k].lrmx=max(tree[k].lrmx,tree[ls].rmx+tree[rs].lmx);tree[k].lmx=max(tree[ls].lmx,tree[rs].lmx+tree[ls].sum);tree[k].rmx=max(tree[rs].rmx,tree[ls].rmx+tree[rs].sum); }inline void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;if(l==r){tree[k].sum=a[l];tree[k].lrmx=tree[k].lmx=tree[k].rmx=max(0ll,a[l]);return;}int mid=(l+r)>>1,ls=k<<1,rs=k<<1|1;build(ls,l,mid);build(rs,mid+1,r);pushup(k); }inline void upd(int k,int l) {if(tree[k].l==tree[k].r){tree[k].sum=a[l];tree[k].lrmx=tree[k].lmx=tree[k].rmx=max(0ll,a[l]);return; }int mid=(tree[k].l+tree[k].r)>>1;if(l<=mid)upd(k<<1,l);elseupd(k<<1|1,l);pushup(k); }inline void mainwork() {ans=0;int l,id;for(int lowx=1;lowx<=totx;lowx++){for(int i=1;i<=toty;i++)a[i]=0;build(1,1,toty);for(int upx=lowx;upx<=totx;upx++){l=tmpy[upx].size();for(int i=0;i<l;i++){id=tmpy[upx][i];a[ay[id]]+=w[id];upd(1,ay[id]);}ans=max(tree[1].lrmx,ans);}} }inline void print() {printf("%lld\n",ans); }int main() {int t;scanf("%d",&t);for(int i=1;i<=t;i++){prework();mainwork();print();}return 0; }
?
1006 Faraway
unsolved.
杭電oj1000答案解析、?
1007 Support or Not
unsolved.
?
1008 TDL
?
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int up=1005; const LL INF=2e18;//! int m; bool check(long long n,long long kn) {int cnt=0; if(n==0)return false; for(long long i=n+1;;i++)if(__gcd(n,i)==1){cnt++;if(cnt==m) return kn==i;}return false; } int main() {int t;scanf("%d",&t);while(t--){LL k,n;scanf("%lld%d",&k,&m);LL ans=INF;for(int i=1;i<=up;i++){n=i^k;if(check(n,i+n)) ans=min(ans,n);}if(ans==INF){puts("-1");}else{printf("%lld\n",ans);}}return 0; }
杭電oj1000題答案。?
1009?Three Investigators
unsolved.
?
1010?Ridiculous Netizens
unsolved.
杭電1000題答案??
1011 11 Dimensions
題解:https://blog.csdn.net/liufengwei1/article/details/98962651
1 #include<bits/stdc++.h> 2 #define maxl 50010 3 using namespace std; 4 5 const long long inf=1e18; 6 const int mod=1e9+7; 7 8 int n,m,q,up=17; 9 int mi[maxl]; 10 int g[21][21]; 11 int go[20][maxl][21],val[20][maxl][21]; 12 long long f[maxl][21]; 13 long long st[20][maxl][21],en[20][maxl][21]; 14 bool can[maxl][10]; 15 char s[maxl]; 16 17 inline long long fix(long long x) 18 { 19 return x<inf?x:inf; 20 } 21 22 inline void prework() 23 { 24 scanf("%d%d%d",&n,&m,&q); 25 scanf("%s",s+1); 26 for(int i=0;i<m;i++) 27 for(int j=0;j<10;j++) 28 g[i][j]=(i*10+j)%m; 29 for(int i=1;i<=n;i++) 30 if(s[i]=='?') 31 for(int j=0;j<10;j++) 32 can[i][j]=true; 33 else 34 { 35 for(int j=0;j<10;j++) 36 can[i][j]=false; 37 can[i][s[i]-'0']=true; 38 } 39 f[n+1][0]=1; 40 for(int j=1;j<m;j++) 41 f[n+1][j]=0; 42 long long tmp,sz,now,sum;int nxt; 43 for(int i=n;i>=1;i--) 44 for(int j=0;j<m;j++) 45 { 46 tmp=0;sz=-1;nxt=-1; 47 for(int k=0;k<10;k++) 48 if(can[i][k]) 49 { 50 now=f[i+1][g[j][k]]; 51 tmp=fix(tmp+now); 52 if(now>sz) nxt=k,sz=now; 53 } 54 f[i][j]=tmp; 55 go[0][i][j]=g[j][nxt]; 56 val[0][i][j]=nxt; 57 sum=0; 58 for(int k=0;k<nxt;k++) 59 if(can[i][k]) 60 sum=fix(sum+f[i+1][g[j][k]]); 61 st[0][i][j]=sum; 62 en[0][i][j]=fix(sum+f[i+1][g[j][nxt]]); 63 } 64 for(int k=1;k<up;k++) 65 for(int i=1;i+(1<<k)<=n+1;i++) 66 for(int j=0;j<m;j++) 67 { 68 int x=go[k-1][i][j],len=1<<(k-1); 69 go[k][i][j]=go[k-1][i+len][x]; 70 val[k][i][j]=(1ll*val[k-1][i][j]*mi[len]+val[k-1][i+len][x])%mod; 71 st[k][i][j]=fix(st[k-1][i][j]+st[k-1][i+len][x]); 72 en[k][i][j]=fix(st[k-1][i][j]+en[k-1][i+len][x]); 73 } 74 } 75 76 inline int query(long long k) 77 { 78 if(k>f[1][0]) return -1; 79 int id=1,res=0,ret=0; 80 long long tmp; 81 while(id<=n) 82 { 83 for(int i=up-1;i>=0;i--) 84 if(id+(1<<i)<=n+1 && st[i][id][res]<k && k<=en[i][id][res]) 85 { 86 ret=(1ll*ret*mi[1<<i]+val[i][id][res])%mod; 87 k-=st[i][id][res]; 88 res=go[i][id][res]; 89 id+=1<<i; 90 } 91 if(id>n) break; 92 for(int i=0;i<10;i++) 93 if(can[id][i]) 94 { 95 tmp=f[id+1][g[res][i]]; 96 if(k>tmp) 97 k-=tmp; 98 else 99 { 100 ret=(10LL*ret+i)%mod; 101 id++; 102 res=g[res][i]; 103 break; 104 } 105 } 106 } 107 return ret; 108 } 109 110 inline void mainwork() 111 { 112 long long x; 113 for(int i=1;i<=q;i++) 114 { 115 scanf("%lld",&x); 116 printf("%d\n",query(x)); 117 } 118 } 119 120 int main() 121 { 122 mi[0]=1; 123 for(int i=1;i<maxl;i++) 124 mi[i]=1ll*10*mi[i-1]%mod; 125 int t; 126 scanf("%d",&t); 127 for(int i=1;i<=t;i++) 128 { 129 prework(); 130 mainwork(); 131 // print(); 132 } 133 return 0; 134 }
?
?
1012 Stay real
#include<bits/stdc++.h> #define maxl 100010 #define mp make_pair using namespace std;int n; int a[maxl]; long long ans1,ans2; typedef pair<int,int> p; priority_queue<p> q; bool in[maxl];inline void prework() {while(!q.empty()) q.pop();scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]),in[i]=true;if(i*2>n)q.push(mp(a[i],i));} }inline void mainwork() {p d;ans1=0,ans2=0;for(int i=1;i<=n;i++){d=q.top();q.pop();in[d.second]=false;if(!in[d.second] && !in[d.second^1])q.push(mp(a[d.second/2],d.second/2));if(i&1)ans1+=d.first;elseans2+=d.first;} }inline void print() {printf("%lld %lld\n",ans1,ans2); }int main() {int t;scanf("%d",&t);for(int i=1;i<=t;i++){prework();mainwork();print();}return 0; }
杭電oj題庫,?
?