长春理工大学第十四届程序设计竞赛
生活随笔
收集整理的這篇文章主要介紹了
长春理工大学第十四届程序设计竞赛
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
Problem A?Rubbish
https://ac.nowcoder.com/acm/contest/912/A
題意：1e5*1e5的棋盤上有n點，求連通塊數(shù)量
C++版本一
題解：坐標(biāo)離散化+坐標(biāo)數(shù)軸化+二分+遞推+并查集
1、對所有坐標(biāo)離散化成數(shù)軸；
2、由左上到右下遞推；
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=1000000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const ll INF = 0x3f3f3f3f3f3f3f; int s,t,n,m,k,p,l,r; ll u,v,a[N]; int x[N],y[N],b[N]; ll ans,cnt,flag,temp,sum; int pre[N]; int find(int x){if(x==pre[x])return x;return pre[x]=find(pre[x]); } void marge(int x,int y){int tx=find(x);int ty=find(y);if(tx!=ty){pre[tx]=ty;} } 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);//int T=0;while(~scanf("%d",&n)){for(int i=1;i<=n;i++)pre[i]=i;for(int i=1;i<=n;i++){scanf("%d%d",&x[i],&y[i]);a[i]=(x[i]-1)*100000ll+y[i];}sort(a+1,a+1+n);for(int i=1;i<=n;i++){u=x[i];v=y[i];ll now=(u-1)*100000ll+v;int ii=lower_bound(a+1,a+n+1,now)-a;if(u<100000ll&&v<100000ll){int jj=lower_bound(a+1,a+n+1,u*100000ll+v+1)-a;if(jj<=n&&a[jj]==u*100000ll+v+1)marge(ii,jj);}if(v<100000ll){int ij=lower_bound(a+1,a+n+1,(u-1)*100000ll+v+1)-a;if(ij<=n&&a[ij]==(u-1)*100000ll+v+1)marge(ii,ij);}if(u<100000ll){int ji=lower_bound(a+1,a+n+1,u*100000ll+v)-a;if(ji<=n&&a[ji]==u*100000ll+v)marge(ii,ji);}if(u<100000ll&&v>1){int jii=lower_bound(a+1,a+n+1,u*100000ll+v-1)-a;if(jii<=n&&a[jii]==u*100000ll+v-1)marge(ii,jii);}if(u>1&&v<100000ll){int jji=lower_bound(a+1,a+n+1,(u-2)*100000ll+v+1)-a;if(jji<=n&&a[jji]==(u-2)*100000ll+v+1)marge(ii,jji);}}ans=0;for(int i=1;i<=n;i++)ans+=(pre[i]==i);cout<<ans<<endl;//printf("%lld\n",ans);}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; } /* 4 1 2 2 1 2 3 3 2 */C++版本二
題解：坐標(biāo)離散化+并查集
將格點按行先列次排序，遍歷過程更新當(dāng)前列的格點中行數(shù)最大格點的下標(biāo)，判斷能否與當(dāng)前點連通，用并查集維護(hù)連通塊。?
#include<bits/stdc++.h> using namespace std; #define LL long long #define PB push_back #define endl '\n' const int N=1e6+7; const int INF=1e8,mod=1e7+7; int n,m,k; struct s{int x,y;int fa; }a[N]; int f[N]; int F(int x){return x==a[x].fa?x:a[x].fa=F(a[x].fa); } void u(int x,int y){x=F(x),y=F(y);if(x==y)return;a[x].fa=y; } bool cmp(s p,s q){if(p.x==q.x)return p.y<q.y;return p.x<q.x; } int main() {cin>>n;for(int i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);}memset(f,-1,sizeof(f));sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++)a[i].fa=i;a[0].y=a[0].x=-1;for(int i=1;i<=n;i++){//如果與前一個格點同行且下標(biāo)差一說明連通if(a[i].y==a[i-1].y+1&&a[i].x==a[i-1].x){u(a[i].fa,a[i-1].fa);}//左上是否有格點if(a[f[a[i].y-1]].x==a[i].x-1){u(a[i].fa,a[f[a[i].y-1]].fa);}//上方是否有if(a[f[a[i].y]].x==a[i].x-1){u(a[i].fa,a[f[a[i].y]].fa);}//右上是否有if(a[f[a[i].y+1]].x==a[i].x-1){u(a[i].fa,a[f[a[i].y+1]].fa);}f[a[i].y]=i;}memset(f,0,sizeof(f));int ans=0;for(int i=1;i<=n;i++){if(!f[F(a[i].fa)]){ans++;f[F(a[i].fa)]=1;}//cout<<i<<' '<<a[i].x<<' '<<a[i].y<<' '<<a[i].fa<<' '<<ans<<endl;}cout<<ans;return 0; }Problem B?Bowling Game
https://ac.nowcoder.com/acm/contest/912/B
題意：藍(lán)色面積S1，黃色面積S2，問球的直徑多大的時候會按照圖中所示卡住。
C++版本一
題解：幾何數(shù)學(xué)
設(shè)d為直徑，r為半徑，S2的邊分別為a，b，c，其中c*c=S1；
證明：
/* *@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; ll 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--){scanf("%lld%lld",&n,&m);printf("%f\n",4*n/(sqrt(m)+sqrt(m+4*n)));//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }C++版本二
題解：二分
對于一個斜邊確定的等腰三角形，兩直角邊差越小面積越大，用s1求出斜邊，然后二分法求兩直角邊的長度，內(nèi)切圓直徑就是直角邊長和減斜邊長。
#include<bits/stdc++.h> using namespace std; #define LL long long #define PB push_back #define endl '\n' int main() {double s1,s2;cin>>s1>>s2;double x=sqrt(s2);double l=0,r=sqrt(2.0)/2*x;while(r-l>=0.0000001){double mid=(l+r)/2;if(mid*sqrt(x*x-mid*mid)/2>s1){r=mid;}else l=mid;}double ans=(l+sqrt(x*x-l*l)-x);printf("%.6lf",ans);return 0; }?
Problem C?REN
https://ac.nowcoder.com/acm/contest/912/C
題意：
題解：
C++版本一
?
Problem D?Capture The Flag
https://ac.nowcoder.com/acm/contest/912/D
題意：
題解：
C++版本一
?
Problem E?Shortest Code
https://ac.nowcoder.com/acm/contest/912/E
題意：去掉沒必要的空格、空行和注釋。
題解：模擬
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; string a; string 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",&n);while(getline(cin,a)){int l=a.size();res="";for(int i=0;i<l;i++)if(a[i]==' ')if(i!=0&&i!=l-1&&isalnum(a[i-1])&&isalnum(a[i+1]))res+=' ';else a[i]=a[i-1];//將空格更新為前一個值else if(i<l-1&&a[i]=='/'&&a[i+1]=='/')break;else res+=a[i];if(res.size())cout<<res<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem F?Successione di Fixoracci
https://ac.nowcoder.com/acm/contest/912/F
題意：
已知a和b的值。現(xiàn)在你只要求出Tn是多少
題解：規(guī)律
C++版本一
題解：
1、任意一個數(shù)被同一個數(shù)異或兩次等于本身。即a^b^b=a；
2、此數(shù)列為 a，b，a^b循環(huá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; ll t,n,m,k,p,l,r,u,v; ll 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--){scanf("%lld%lld%lld",&n,&m,&k);if(k%3==0)ans=n;if(k%3==1)ans=m;if(k%3==2)ans=n^m;cout<<ans<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem G?Segment Tree
https://ac.nowcoder.com/acm/contest/912/G
題意：
題解：
C++版本一
?
Problem H?Arithmetic Sequence
https://ac.nowcoder.com/acm/contest/912/H
題意：輸出一個等差數(shù)列，使得數(shù)列和等于X
題解：沒有要求數(shù)列長度，因此直接輸出x
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--){scanf("%d",&n);cout<<1<<endl;cout<<n<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem I?Fate Grand Order
https://ac.nowcoder.com/acm/contest/912/I
題意：最多n/3個活動，使得期望最大
題解：貪心
每張卡片帶來開心值的期望為抽中概率乘開心值，按期望排序貪心即可
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,l,r,u,v; int ans,cnt,flag,temp,sum; string str=""; struct node{double p,x;double q;int id;bool operator <(const node&S)const{return q>S.q;} }e[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(t--){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%lf",&e[i].p),e[i].id=i,str+='0';for(int i=1;i<=m;i++)scanf("%lf",&e[i].x),e[i].q=e[i].x*e[i].p;n/=3;sort(e+1,e+m+1);for(int i=1;i<=min(n,m);i++)str[e[i].id-1]='1';cout<<str<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem J?Printout
https://ac.nowcoder.com/acm/contest/912/J
題意：
題解：模擬
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; double ans,cnt,flag,temp,sum; int a[N]; double 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--){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d",&a[i]);for(int i=1;i<=m;i++)scanf("%lf",&b[i]);a[0]=1;for(int i=1;i<=m;i++){if(n<=a[i]){ans=n*b[i];for(int j=i+1;j<=m;j++){ans=min(ans,a[j-1]*b[j]);}break;}}cout<<ans<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem K?Master of Graph
https://ac.nowcoder.com/acm/contest/912/K
題意：區(qū)間修改+區(qū)間查詢
題解：線段樹+標(biāo)記
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=200000+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,q; int ans,cnt,flag,temp,sum; char str; struct node{}; ll tree[N<<2]; bool tag[N<<2]; ll f(ll x){//計算f(x)ll re=0;while(x){re+=x%10;x/=10;}return re; } void pushup(int rt){tree[rt]=tree[rt<<1]+tree[rt<<1|1];tag[rt]=tag[rt<<1]&&tag[rt<<1|1]; } void build(int l,int r,int rt){if(l==r){scanf("%lld",&tree[rt]);tag[rt]=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,int R){if(tag[rt])return;if(l==r){tree[rt]=f(tree[rt]);if(tree[rt]<10)tag[rt]=1;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(L<=l&&r<=R){return tree[rt];}int mid=(l+r)>>1;if(R<=mid)return query(l,mid,rt<<1,L,R);else if(L>mid)return query(mid+1,r,rt<<1|1,L,R);else return query(l,mid,rt<<1,L,R)+query(mid+1,r,rt<<1|1,L,R); } 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);memset(tree,0,sizeof(tree));build(1,n,1);while(m--)scanf("%d%d",&u,&v);scanf("%d",&q);while(q--){scanf("%d%d%d",&t,&l,&r);if(t){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 L?Homework Stream
https://ac.nowcoder.com/acm/contest/912/L
題意：編號為k的作業(yè)依賴于哪些作業(yè)，以及哪些作業(yè)依賴于編號為k的作業(yè)。
題解：模擬
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; vector<int>a,b; void print(vector<int>p){for(int i=0;i<p.size();i++){printf("%d%c",p[i]," \n"[i==p.size()-1]);}if(p.size()==0)cout<<endl; } 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%d",&n,&m,&k);for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);if(u==k)a.push_back(v);if(v==k)b.push_back(u);}print(a);print(b);//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem M?Orx Zone
https://ac.nowcoder.com/acm/contest/912/M
題意：
題解：對于1-n為左邊界的情況恭喜就是(n+1-當(dāng)前最近的’x’和’r’的下標(biāo)的較大值）
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=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,x[N],r[N],u,v; ll ans,cnt,flag,temp,sum; char a[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(t--){//scanf("%d",&n);scanf("%s",a+1);int len=strlen(a+1);x[len+1]=r[len+1]=len+1;for(int i=len;i>=1;i--){x[i]=(a[i]=='x'?i:x[i+1]);//在該點后最近的xr[i]=(a[i]=='r'?i:r[i+1]);//在該點后最近的r}for(int i=1;i<=len;i++)ans+=len-max(x[i],r[i])+1;cout<<ans<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }?
總結(jié)
以上是生活随笔為你收集整理的长春理工大学第十四届程序设计竞赛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Nauuo and Circle
- 下一篇： Divide it!