浙江理工大学2019年4月赛
生活随笔
收集整理的這篇文章主要介紹了
浙江理工大学2019年4月赛
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
Problem A?我不會(huì)做
比賽地址：http://47.96.116.66/problem.php?cid=1222&pid=0?
補(bǔ)題地址：http://47.96.116.66/problem.php?id=1908
題解：
1、按題意輸出，請(qǐng)注意”??(“一起輸出, 在評(píng)測(cè)中會(huì)被當(dāng)成’[‘，所以要分開輸出；
2、看清楚什么時(shí)候向上取整，什么時(shí)候向下取整；
3、二進(jìn)制1的數(shù)量其實(shí)有個(gè)函數(shù)可以用；
C++版本一
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int a[N]; char str; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);scanf("%d",&t);while(t--){double nx;scanf("%lf",&nx);//nx=(1<<20);n=nx;sum=0;temp=0;if(nx==0){cout<<"Areyou";cout<<"sure";cout<<"?";cout<<"?";cout<<")";cout<<":";cout<<"?";cout<<"?";cout<<"?"<<endl;continue;}while(n){sum++;temp+=(n%2);n/=2;}//cout<<sum<<temp<<endl;if(sum==temp&&sum!=0){cout<<sum<<endl;continue;}else{n=nx;if(n!=nx){n++;}}cout<<"Areyou";for(int i=1;i<=n;i++){cout<<"really";}cout<<"sure";cout<<"?";cout<<"?";cout<<")";cout<<":";for(int i=1;i<=n;i++){cout<<"pardon";}cout<<"?";cout<<"?";cout<<"?"<<endl;} #ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem B?我不能做
?
比賽地址：http://47.96.116.66/problem.php?cid=1222&pid=1?
補(bǔ)題地址：http://47.96.116.66/problem.php?id=1909
題解：把點(diǎn)離散化出來之后， 把相鄰兩點(diǎn)之間的線段全部摳出來， 用這些線段建線段樹直接維護(hù)就好了。
1、整整寫了一天（劃掉）；
2、扣線段 離散化 例如：所有點(diǎn)以后為1? 5? 10? ?應(yīng)該加點(diǎn)變成 1 2? 5? 6 10 ，離散化?1([1,1]) 2([2,4]) 3([5,5]) 4([6,9]) 5([10,10])；
PS：點(diǎn)（區(qū)間）
3、卡內(nèi)存，單單找合適的內(nèi)存設(shè)置就搞了半小時(shí)；
4、區(qū)間更新，需要一點(diǎn)點(diǎn)等差數(shù)列的知識(shí)，lazy需要兩個(gè)數(shù)組初項(xiàng)（lazy）、公差（tag）；
5、tree數(shù)組存儲(chǔ)val和左右端點(diǎn)，（為什么代碼是op?因?yàn)槲覒械酶?#xff0c;之前和e公用一個(gè)結(jié)構(gòu)體）；
6、tree可以偷懶取3倍；
7、少點(diǎn)ll的數(shù)組，運(yùn)算過程ll；
8、想不明白STD的64MB2252MS；
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=1500000+10; const int M=500000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum[M*2],Y[N]; char str; struct node{int op,l,r; }e[M]; struct Node{ll op;int l,r; }tree[N*3]; int lazy[N*3]; int tag[N*3]; void pushup(int rt){tree[rt].op=(tree[rt<<1].op+tree[rt<<1|1].op)%MOD; } void pushdown(int rt){if(lazy[rt]){//cout<<tree[rt<<1].op<<" "<<tree[rt<<1|1].op<<endl;//cout<<tree[rt<<1].l<<" "<<tree[rt].r<<" "<<tree[rt<<1|1].l<<" "<<tree[rt].r<<endl;//cout<<lazy[rt]<<" "<<lazy[rt<<1]<<" "<<lazy[rt<<1|1]<<" "<<endl;lazy[rt<<1]=(ll)(lazy[rt<<1]+lazy[rt])%MOD;lazy[rt<<1|1]=(ll)(lazy[rt<<1|1]+lazy[rt]+(ll)(tree[rt<<1|1].l-tree[rt<<1].l)*tag[rt]%MOD)%MOD;tag[rt<<1]=(ll)(tag[rt<<1]+tag[rt])%MOD;tag[rt<<1|1]=(ll)(tag[rt<<1|1]+tag[rt])%MOD;//cout<<lazy[rt<<1]<<" "<<lazy[rt<<1|1]<<" "<<endl;tree[rt<<1].op = (ll)(tree[rt<<1].op +((ll)(lazy[rt]-tag[rt])*(tree[rt<<1].r-tree[rt<<1].l+1)%MOD)+(ll)(tag[rt]*((ll)(tree[rt<<1].r-tree[rt<<1].l+1)*(tree[rt<<1].r-tree[rt<<1].l+2)/2%MOD))%MOD)%MOD;tree[rt<<1|1].op = (ll)(tree[rt<<1|1].op +(((lazy[rt]+((ll)(tree[rt<<1|1].l-tree[rt<<1].l)*tag[rt]%MOD)-tag[rt])%MOD)*(tree[rt<<1|1].r-tree[rt<<1|1].l+1)%MOD)+(tag[rt]*((ll)(tree[rt<<1|1].r-tree[rt<<1|1].l+1)*(tree[rt<<1|1].r-tree[rt<<1|1].l+2)/2)%MOD)%MOD)%MOD;//cout<<tree[rt<<1].op<<" "<<tree[rt<<1|1].op<<endl;tag[rt]=0;lazy[rt]=0;} } void build(int l,int r,int rt){if(l==r){tree[rt].l=Y[l];tree[rt].r=Y[l+1]-1;tree[rt].op=0;return;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);tree[rt].l=tree[rt<<1].l;tree[rt].r=tree[rt<<1|1].r;tree[rt].op=0;pushup(rt); } void updata(int l,int r,int rt,int L,int R,ll C){//cout<<tree[rt].l<<" "<<tree[rt].r<<" "<<tree[rt].op<<" "<<lazy[rt]<<" "<<endl;if( L <= l && r<= R){//cout<<C<<endl;tree[rt].op = (ll)(tree[rt].op+((ll)(tree[rt].l-C)*(tree[rt].r-tree[rt].l+1)%MOD+(((ll)(tree[rt].r-tree[rt].l+1)*(tree[rt].r-tree[rt].l+2)/2)%MOD))%MOD)%MOD; // 染成 c 的顏色lazy[rt] = (ll)(lazy[rt]+(tree[rt].l-C+1))%MOD;tag[rt]=(tag[rt]+1)%MOD;//cout<<tree[rt].op<<endl;return;}pushdown(rt);int mid=(l+r)>>1;if(L<=mid)updata(l,mid,rt<<1,L,R,C);if(R>mid) updata(mid+1,r,rt<<1|1,L,R,C);pushup(rt); } ll query(int l,int r,int rt,int L,int R){//cout<<l<<" "<<r<<" "<<tree[rt].op<<" "<<lazy[rt]<<" "<<tag[rt]<<endl;if(L <= l && r<= R){return tree[rt].op;}pushdown(rt);int mid=(l+r)>>1;ll res=0;if(L<=mid)res=(res+query(l,mid,rt<<1,L,R))%MOD;if(R>mid)res=(res+query(mid+1,r,rt<<1|1,L,R))%MOD;return res; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d%d",&n,&m);cnt=0;for(int i=1;i<=m;i++){scanf("%d%d%d",&e[i].op,&e[i].l,&e[i].r);sum[++cnt]=e[i].l;sum[++cnt]=e[i].r;}int tot=0;sort(sum+1,sum+cnt+1);//X[++tot].l=sum[1],X[tot].r=sum[1];Y[++tot]=sum[1];for(int i=2;i<=cnt;i++){if(sum[i-1]!=sum[i]){if(sum[i]-sum[i-1]>1){//X[++tot].l=sum[i-1]+1;Y[++tot]=sum[i-1]+1;//X[tot].r=sum[i]-1;}//X[++tot].l=sum[i],X[tot].r=sum[i];Y[++tot]=sum[i];}}Y[tot+1]=Y[tot]+1;build(1,tot,1);for(int i=1;i<=m;i++){int l = lower_bound(Y+1,Y+tot+1,e[i].l)-Y;int r = lower_bound(Y+1,Y+tot+1,e[i].r)-Y;//cout<<l<<" "<<r<<endl;if(e[i].op==1){updata(1,tot,1,l,r,e[i].l);}else{cout<<(query(1,tot,1,l,r)+MOD)%MOD<<endl;}}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; } /* 10 5 1 1 10 1 1 5 1 6 10 2 1 10 2 5 61000000000 5 1 1 1000000000 1 1 500000000 1 500000000 1000000000 2 1 1000000000 2 2 1000000000 */Problem C?我想做
比賽地址：http://47.96.116.66/problem.php?cid=1222&pid=2
補(bǔ)題地址：http://47.96.116.66/problem.php?id=1910
題解：
1、存在i can't't't't't't...的情況，i couldn't同理；
2、存在i can gao ‘t 的情況，i couldn't同理；
3、while多次處理，直到不能進(jìn)行任何存在；
4、"duxing201606nb!".最后處理；
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int a[N]; char str0[N],st1[20]="i can't",st2[20]="i couldn't"; string str,str1,str2; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);while(gets(str0)!=NULL){//scanf("%d",&n);str=str0;flag=1;while(flag){flag=0;int pos=0;while(str[pos]==' ')flag=1,pos++;str1="";for(int i=pos;i<str.size();i++){if(str[i]==' '&&!isalnum(str[i+1])){flag=1;continue;}str1+=str[i];}str2="";for(int i=0;i<str1.size();i++){if(i==0&&str1[i]=='g'&&str1[i+1]=='a'&&str1[i+2]=='o'&&!isalnum(str1[i+3])){flag=1;i+=2;continue;}if(i&&!isalnum(str1[i-1])&&str1[i]=='g'&&str1[i+1]=='a'&&str1[i+2]=='o'&&!isalnum(str1[i+3])){flag=1;i+=2;continue;}if(str1[i]=='i'){temp=1;for(int j=0;j<7;j++){if(str1[i+j]!=st1[j]){temp=0;break;}}if(temp){i+=6;str2+="i can";while(str1[i+1]=='\''&&str1[i+2]=='t')i+=2;flag=1;continue;}temp=1;for(int j=0;j<10;j++){if(str1[i+j]!=st2[j]){temp=0;break;}}if(temp){i+=9;str2+="i could";while(str1[i+1]=='n'&&str1[i+2]=='\''&&str1[i+3]=='t')i+=3;flag=1;continue;}}str2+=str1[i];}str=str2;//cout<<str<<endl;}str1="";for(int i=0;i<str.size();i++){str1+=str[i];if(str[i]=='.'){str1+="duxing201606nb!";}}cout<<str1<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }?
?
Problem D?我得試著去做
比賽地址：http://47.96.116.66/problem.php?cid=1222&pid=3
補(bǔ)題地址：http://47.96.116.66/problem.php?id=1911
題解：
線篩求phi，線段樹維護(hù)a的區(qū)間和，由于phi最多執(zhí)行l(wèi)og次就會(huì)變成1，直接暴力維護(hù)到葉子節(jié)點(diǎn)。判斷一下是不是整個(gè)區(qū)間都是1，是的話就不用繼續(xù)走了。
1、歐拉函數(shù)線性篩；
2、1e7的轉(zhuǎn)換范圍內(nèi)最多18次；
3、線段樹優(yōu)化。
參考文章：歐拉函數(shù)?? 線段樹
?
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=500000+10; const int M=10000000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int f[M],prime[M],pre[N]; ll tree[N<<2]; void init(){f[1]=1;prime[0]=prime[1]=1;for(int i=2;i<=1e7;i++){if(prime[i]==0){pre[++cnt]=i;f[i]=i-1;}for(int j=1;j<=cnt&&pre[j]*i<=1e7;j++){prime[i*pre[j]]=1;f[i*pre[j]]=f[i]*f[pre[j]];if(i%pre[j]==0){f[i*pre[j]]=f[i]*(f[pre[j]]+1);break;}}} } void pushup(int rt){tree[rt]=tree[rt<<1]+tree[rt<<1|1]; } void build(int l,int r,int rt){if(l==r){scanf("%lld",&tree[rt]);return;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);pushup(rt);} void updata(int l,int r,int rt,int L,int R){if(tree[rt]==r-l+1)return;if(l==r){tree[rt]=f[tree[rt]];return;}int mid=(l+r)>>1;if(L<=mid)updata(l,mid,rt<<1,L,R);if(R>mid)updata(mid+1,r,rt<<1|1,L,R);pushup(rt); } ll query(int l,int r,int rt,int L,int R){if(tree[rt]==r-l+1&&l<=L&&R<=r){return R-L+1;}if(L<=l&&r<=R){return tree[rt];}int mid=(l+r)>>1;ll res=0;if(L<=mid)res+=query(l,mid,rt<<1,L,R);if(R>mid)res+=query(mid+1,r,rt<<1|1,L,R);return res; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);init();while(~scanf("%d",&n)){memset(tree,0,sizeof(tree));build(1,n,1);scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&k,&l,&r);if(k==1){updata(1,n,1,l,r);}else{cout<<query(1,n,1,l,r)<<endl;}}}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem E?我好像不會(huì)做
比賽地址：http://47.96.116.66/problem.php?cid=1222&pid=4
?
補(bǔ)題地址：http://47.96.116.66/problem.php?id=1912
題解：
對(duì)于每一個(gè)磚記錄下左邊可以的第一塊磚是哪一塊，右邊可用的第一塊磚是那一塊。
在沒有取走任何磚的前提下，對(duì)于第i塊磚來說， l[i] = i-1, r[i] = i+1；
然后我們枚舉1-n顏色并且沒有被取的磚在那些位置i，拿完之后看一下l[i]\r[i]是不是所需要的磚,如果是就直接拿走，不是就直接從當(dāng)前位置走到下一個(gè)可以取的位置。
在每次拿磚的時(shí)候，隨時(shí)更新L[i], r[i]。
每次經(jīng)過拿過的磚的時(shí)候，將L[i] 和 r[i] 還原為初始值。
這樣一直模擬就可以了。
答案為ans*(n-1)+n的位置；
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l[N],r[N],u,v; ll ans,cnt,flag,temp,sum; int a[N],vis[N],b[N]; char str; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){while(~scanf("%d",&n)){memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){scanf("%d",&a[i]);l[i]=i-1;r[i]=i+1;b[a[i]]=i;}ans=0;for(int i=1;i<=n;i++){if(vis[i]==0){int now=i;ans++;for(int pos=b[i];pos<=n;b[now]>=r[pos]?pos=b[now]:pos=n+1){l[pos]=pos-1;r[pos]=pos+1;if(a[pos]==now){vis[now]=1;now++;while(a[l[pos]]==now||a[r[pos]]==now){if(a[l[pos]]==now){l[pos]--;vis[now]=1;now++;}if(a[r[pos]]==now){r[pos]++;vis[now]=1;now++;}}}}}}cout<<ans*n-n+b[n]<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }?
Problem F?我好像會(huì)做了
比賽地址：http://47.96.116.66/problem.php?cid=1222&pid=5
補(bǔ)題地址：http://47.96.116.66/problem.php?id=1913
題解：可以通過相似三角形得出線段比值關(guān)系，從而證明出反向延長(zhǎng)線將三角形分割成兩個(gè)面積一樣的三角形，則該線即是中線交點(diǎn)，初中時(shí)老師說過，中線交點(diǎn)是重心，那么，重心交點(diǎn)便是( (x1+x2+x3)/3, (y1+y2+y3)/3 ),最后將坐標(biāo)答案乘上3的逆元即可。
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; ll x,y,x2,y2,x3,y3; char str; struct node{}; ll POW(ll a,ll b,ll c){ll res=1;ll base=a%c;while(b){if(b&1)res=(res*base)%c;base=(base*base)%c;b>>=1;}return res; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%lld%lld%lld%lld%lld%lld",&x,&y,&x2,&y2,&x3,&y3);ll X=x+x2+x3;ll Y=y+y2+y3;ll inv=POW(3,MOD-2,MOD);if(X%3==0){cout<<X/3;}else{cout<<(X*inv)%MOD;}cout<<" ";if(Y%3==0){cout<<Y/3<<endl;}else{cout<<(Y*inv)%MOD<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }?
?
Problem G?我會(huì)盡量做
比賽地址：http://47.96.116.66/problem.php?cid=1222&pid=6
補(bǔ)題地址：http://47.96.116.66/problem.php?id=1914
題解：
1、map；
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int a[N]; int b[N]; char str[10]; map<string,int>mp; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s%d",str,&t);if(!mp[str])mp[str]=++cnt;a[mp[str]]=t;}//cout<<cnt<<endl;for(int i=1;i<=m;i++){scanf("%d%s%d",&k,str,&t);if(k==1){b[mp[str]]=max(t,b[mp[str]]);}else{a[mp[str]]+=t;}}for(int i=1;i<=cnt;i++){if(a[i]<=b[i])ans++;}cout<<ans<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem H?我能做
比賽地址：http://47.96.116.66/problem.php?cid=1222&pid=7
?
補(bǔ)題地址：http://47.96.116.66/problem.php?id=1915
C++版本一
題解：暴力方法（數(shù)據(jù)弱）
1、標(biāo)記這個(gè)員工有沒有工作；
2、向查詢boss有沒有工作并求最小值；
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=50000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v,op; int ans,cnt,flag,temp,sum; bool vis[N]; struct node{}; int pre[N]; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);while(~scanf("%d%d",&n,&m)){for(int i=i;i<=n;i++)pre[i]=i;memset(vis,0,sizeof(vis));for(int i=2;i<=n;i++){scanf("%d",&u);pre[i]=u;}for(int i=1;i<=m;i++){scanf("%d%d",&op,&u);if(op==1){vis[u]=1;}else if(op==2){vis[u]=0;}else{ans=INF;while(pre[u]!=u){if(vis[u]){ans=min(ans,u);}u=pre[u];}if(vis[u]){ans=min(ans,u);}cout<<(ans==INF?-1:ans)<<endl;}}}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }C++版本二
題解：
線段樹維護(hù)子樹。
先求出dfs序。
每次1 X的時(shí)候，都往 in[x] out[x]這段區(qū)間內(nèi)插入x
每次2 X的時(shí)候，都從 in[x] out[x]這段區(qū)間內(nèi)刪除x
每次3 X的時(shí)候，和李超樹類似，在包含這個(gè)in[x]的所有區(qū)間中找到最小值。
最小值用set去維護(hù)。
最后的復(fù)雜度就是O(n*logn*logn).
?
?
?
Problem I?我會(huì)做
比賽地址：http://47.96.116.66/problem.php?cid=1222&pid=8
補(bǔ)題地址：http://47.96.116.66/problem.php?id=1916
題解：（真心看不懂題解，怕不是體育老師教的語文？）
可以先將偶數(shù)位置設(shè)定為自己選取，奇數(shù)位置為對(duì)方選取。然后，我們發(fā)現(xiàn)，第i位，可以與之后（i到n）的一個(gè)對(duì)方選取的物品進(jìn)行交換，交換之后還滿足之前的性質(zhì)。那么這個(gè)過程可以用線段樹或者multiset之類的完成。
當(dāng)然，也可以用優(yōu)先隊(duì)列什么的亂搞，倒著模擬。
C++版本一
題解：優(yōu)先隊(duì)列
從后往前取的模擬，奇數(shù)位置的就放優(yōu)先隊(duì)列里，然后偶數(shù)位置的話就和優(yōu)先隊(duì)列里最大的比，如果小于的話，就把最大那個(gè)加進(jìn)答案，然后刪除，再把偶數(shù)位的那個(gè)放進(jìn)去，大于就直接放原來偶數(shù)位的，說白了就是第i位，要比后面任何一奇數(shù)位大；
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=1000000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; ll ans,cnt,flag,temp,sum; ll a[N]; char str; struct node{ll id,val;bool operator <(const node &S)const{if(val==S.val){return id>S.id;}return val<S.val;} }x; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){while(~scanf("%d",&n)){ans=0;priority_queue<node>q;while(!q.empty()){q.pop();}for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}for(int i=n;i>=1;i--){if(i%2==0){if(!q.empty()&&q.top().val>a[i]){x=q.top();q.pop();swap(a[i],x.val);q.push(x);}ans+=a[i];}else{x.id=i;x.val=a[i];q.push(x);}}cout<<ans<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }C++版本二
線段樹+結(jié)構(gòu)體
（快還是優(yōu)先隊(duì)列快一點(diǎn)）
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=1000000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; ll ans,cnt,flag,temp,sum; ll a[N]; char str; struct node{ll id,val;bool operator <(const node &S)const{if(val==S.val){return id>S.id;}return val<S.val;} }tree[N<<2],x; void pushup(int rt){tree[rt]=max(tree[rt<<1],tree[rt<<1|1]); } void build(int l,int r,int rt){if(l==r){tree[rt].id=l;tree[rt].val=0;return;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);pushup(rt);} void updata(int l,int r,int rt,int L,ll C){if(l==r){tree[rt].val=C;return;}int mid=(l+r)>>1;if(L<=mid)updata(l,mid,rt<<1,L,C);else updata(mid+1,r,rt<<1|1,L,C);pushup(rt); } node query(int l,int r,int rt,int L,int R){if(L<=l&&r<=R){return tree[rt];}int mid=(l+r)>>1;node res;res.val=0;if(L<=mid)res=max(res,query(l,mid,rt<<1,L,R));if(R>mid)res=max(res,query(mid+1,r,rt<<1|1,L,R));return res; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){while(~scanf("%d",&n)){ans=0;build(1,n,1);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}for(int i=n;i>=1;i--){if(i%2==0){x=query(1,n,1,i,n);if(x.val>a[i]){updata(1,n,1,x.id,a[i]);a[i]=x.val;}ans+=a[i];}else{updata(1,n,1,i,a[i]);}}cout<<ans<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }C++版本三
multiset我是真不會(huì)
?
Problem J?我做到了
比賽地址：http://47.96.116.66/problem.php?cid=1222&pid=9
補(bǔ)題地址：http://47.96.116.66/problem.php?id=1917
題解：我們可以隨便在紙上畫出一些點(diǎn)，如果我們用一個(gè)定長(zhǎng)圓去套這些點(diǎn)，我們可以發(fā)現(xiàn)，圓上至少有兩個(gè)點(diǎn)，則我們可以得出，最大值一定在任意兩個(gè)點(diǎn)確定的半徑為r的圓內(nèi)，那我我們可以n^2枚舉出所有圓心，判斷剩下n-2個(gè)點(diǎn)是否在圓內(nèi)，更新美味度的最大值即可，注意，枚舉圓上的兩個(gè)點(diǎn)時(shí)候，注意判斷兩個(gè)點(diǎn)之間距離是否能夠組成一個(gè)半徑為r的圓，以及兩個(gè)點(diǎn)可以確定1~2個(gè)圓。
1、百度的方法求圓心是不行的（精度原因），正確方法是用斜率求出相對(duì)于枚舉的兩個(gè)點(diǎn)的中點(diǎn)的增量dx dy；
2、long double是錯(cuò)的；
3、枚舉的兩個(gè)點(diǎn)縱坐標(biāo)相同時(shí)需要特判；
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; ll ans,cnt,flag,temp,sum; char str; struct node{ll x,y,v; }e[N]; double dist(double x,double y,double x2,double y2){return sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2)); } ll sloved(int i,int j){if(dist(e[i].x,e[i].y,e[j].x,e[j].y)>2*r){return 0;}double x1 = e[i].x, y11 = e[i].y, x2 = e[j].x, y2 = e[j].y, R = r;double y01 = 0, x01 = 0, x02 = 0, y02 = 0;if(y11==y2){x02=x01=(x1+x2)/2;y01=sqrt(R*R-(x1-x2)*(x1-x2)/4)+y11;y02=-sqrt(R*R-(x1-x2)*(x1-x2)/4)+y2;}else{double dis=dist(x1,y11,x2,y2)/2;double k=-(x1-x2)/(y11-y2);double d=sqrt(R*R-dis*dis);double x0=(x1+x2)/2,y0=(y11+y2)/2;double dy=sin(atan(k))*d,dx=cos(atan(k))*d;x01=x0+dx;y01=y0+dy;x02=x0-dx;y02=y0-dy;}ll res0=0;//cout<<i<<" "<<j<<endl;//cout<<x01<<" "<<y01<<endl;for(int i=1;i<=n;i++){if(dist(x01,y01,e[i].x,e[i].y)<=R){res0+=e[i].v;}}ll res1=0;for(int i=1;i<=n;i++){if(dist(x02,y02,e[i].x,e[i].y)<=R){res1+=e[i].v;}}return max(res0,res1); } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){while(~scanf("%d%d",&n,&r)){ans=0;for(int i=1;i<=n;i++){scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].v);}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){ans=max(ans,sloved(i,j));}}cout<<ans<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }?
總結(jié)
以上是生活随笔為你收集整理的浙江理工大学2019年4月赛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： The Preliminary Cont
- 下一篇： Reverse a Substring