长春理工大学第十四届程序设计竞赛
Problem A Rubbish
https://ac.nowcoder.com/acm/contest/912/A
题意：1e5*1e5的棋盘上有n点，求连通块数量
C++版本一
题解：坐标离散化+坐标数轴化+二分+递推+并查集
1、对所有坐标离散化成数轴；
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 DEBUG
freopen("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 DEBUG
printf("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++版本二
题解：坐标离散化+并查集
将格点按行先列次排序，遍历过程更新当前列的格点中行数最大格点的下标，判断能否与当前点连通，用并查集维护连通块。
#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++){
//如果与前一个格点同行且下标差一说明连通
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
题意：蓝色面积S1，黄色面积S2，问球的直径多大的时候会按照图中所示卡住。
C++版本一
题解：几何数学
设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 DEBUG
freopen("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 DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
题解：二分
对于一个斜边确定的等腰三角形，两直角边差越小面积越大，用s1求出斜边，然后二分法求两直角边的长度，内切圆直径就是直角边长和减斜边长。
#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 DEBUG
freopen("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 DEBUG
printf("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的值。现在你只要求出Tn是多少
题解：规律
C++版本一
题解：
1、任意一个数被同一个数异或两次等于本身。即a^b^b=a；
2、此数列为 a，b，a^b循环
/*
*@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 DEBUG
freopen("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 DEBUG
printf("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
题意：输出一个等差数列，使得数列和等于X
题解：没有要求数列长度，因此直接输出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 DEBUG
freopen("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 DEBUG
printf("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 DEBUG
freopen("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 DEBUG
printf("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 DEBUG
freopen("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 DEBUG
printf("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
题意：区间修改+区间查询
题解：线段树+标记
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 DEBUG
freopen("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 DEBUG
printf("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的作业依赖于哪些作业，以及哪些作业依赖于编号为k的作业。
题解：模拟
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 DEBUG
freopen("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 DEBUG
printf("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-当前最近的’x’和’r’的下标的较大值）
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 DEBUG
freopen("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]);//在该点后最近的x
r[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 DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
微软公司福利 59人发布
查看34道真题和解析