第五届新疆省ACM-ICPC程序设计竞赛
Problem A Good 的集合
https://ac.nowcoder.com/acm/contest/911/A
题意：输出最大的 good 的点集大小。
题解：枚举
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;
pair<int,int> a[9]={pair<int,int>(0,0),pair<int,int>(0,1),pair<int,int>(0,2),
pair<int,int>(1,0),pair<int,int>(1,1),pair<int,int>(1,2),
pair<int,int>(2,0),pair<int,int>(2,1),pair<int,int>(2,2)};
map<pair<int,int>,int>mp;
int check(int x){
for(int i=0;i<9;i++){
if((x>>i)&1)
for(int j=i+1;j<9;j++){
if((x>>j)&1)
for(int c=j+1;c<9;c++){
if((x>>c)&1){
if((a[i].first+a[j].first+a[c].first)%3==0&&(a[i].second+a[j].second+a[c].second)%3==0)return 0;
}
}
}
}
return 1;
}
void dfs(int x,int y,int z){
if(z==9)return;
if(check(x|(1<<z))&&mp[a[z]]){
int cnt=min(mp[a[z]],2);
ans=max(ans,y+cnt);
dfs(x|(1<<z),y+cnt,z+1);
}
dfs(x,y,z+1);
}
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--){
for(int i=0;i<9;i++){
mp[a[i]]=0;
}
cin>>n;
int x,y;
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
mp[pair<int,int>(x%3,y%3)]++;
}
dfs(0,0,0);
cout<<ans<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem B 狂赌之渊
https://ac.nowcoder.com/acm/contest/911/B
题意：
题解：博弈论
C++版本一
题解：当和为奇数时为n，否则为0
/*
*@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);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
cout<<(sum&1?n:0)<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem C 随机独立集
题意：
题解：
C++版本一
Problem D O(n!)
https://ac.nowcoder.com/acm/contest/911/D
题意：有 n件商品，第 i件商品价格为 a[i]，购买后，其它所有未购买的商品价格乘上 p[i]，现在要买下所有商品，输出最小耗费。
题解：排序+贪心
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;
char str;
struct node{
int a;
double p;
bool operator<(const node &S)const{
return S.a+a*S.p>S.a*p+a;
}
}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",&n);
for(int i=1;i<=n;i++)scanf("%d%lf",&e[i].a,&e[i].p);
sort(e+1,e+n+1);
double P=1.0;
for(int i=1;i<=n;i++){
ans+=e[i].a*P;
P*=e[i].p;
}
printf("%f\n",ans);
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem E 斐波那契串
https://ac.nowcoder.com/acm/contest/911/E
题意：输出F[x]的第 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;
ll t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
ll f[1000];
string str1,str2;
struct node{};
char sloved(ll x,ll y){//out<<x<<y<<endl;
if(x==1)
return str1[y-1];
if(x==2)
return str2[y-1];
return y<=f[x-1]?sloved(x-1,y):sloved(x-2,y-f[x-1]);
}
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--){
cin>>str1>>str2;
f[1]=str1.size();
f[2]=str2.size();
cnt=100;
for(int i=3;i<=100;i++){
f[i]=f[i-1]+f[i-2];//cout<<f[i]<<endl;
if(f[i]>=1e18){cnt=i;break;}
}
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&p,&k);
cout<<sloved(min(p,cnt),k)<<endl;
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem F 无交集的圆
https://ac.nowcoder.com/acm/contest/911/F
题意：Y轴上有许多圆，所有圆的圆心位于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;
ll ans,cnt,flag,temp,sum;
int a[N],b[N];
char str;
struct node{
double p,r;
}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",&n);
for(int i=1;i<=n;i++)scanf("%lf%lf",&e[i].p,&e[i].r),a[i]=e[i].p-e[i].r,b[i]=e[i].p+e[i].r;
sort(a+1,a+n+1);
sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
ans+=(lower_bound(b+1,b+n+1,e[i].p-e[i].r)-b)+n-(upper_bound(a+1,a+n+1,e[i].p+e[i].r)-a);
//cout<<ans<<endl;
}
cout<<ans/2<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem G 最长递增长度
https://ac.nowcoder.com/acm/contest/911/G
题意：最长严格递增子序列的长度
题解：最长的严格递增子序列
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 dp[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);
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++)scanf("%d",&a[i]),*lower_bound(dp+1,dp+n+1,a[i])=a[i];
printf("%lld\n",lower_bound(dp+1,dp+n+1,INF)-(dp+1));
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem H 虚无的后缀
https://ac.nowcoder.com/acm/contest/911/H
题意：给出 n 个数字，第 i 个数字为 a[i]，我们从中选出 k 个数字，使得乘积后缀 0 的个数最多。
题解：DP+01背包
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=5000+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 a[N];
int dp[200+10][N];
char str;
struct node{
int cnt5,cnt2;
}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);
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
while(a[i]%2==0){
a[i]/=2;
e[i].cnt2++;
}
while(a[i]%5==0){
a[i]/=5;
e[i].cnt5++;
}
for(int j=m;j>=1;j--){
for(int k=26*200;k>=e[i].cnt5;k--){
if(dp[j-1][k-e[i].cnt5]!=-1){
dp[j][k]=max(dp[j][k],dp[j-1][k-e[i].cnt5]+e[i].cnt2);
ans=max(ans,min(dp[m][k],k));//cout<<j<<" "<<k<<" "<<ans<<" "<<dp[j][k]<<endl;
}
}
}
}
cout<<ans<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem I 大吉大利
https://ac.nowcoder.com/acm/contest/911/I
题意：需要弃置的最少金币
题解：二分
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],b[N];
char str;
struct node{};
bool check(int mid){
int c=a[1]-mid;
cnt=0;
for(int i=2;i<=n;i++){
if(a[i]>c){//cout<<cnt<<endl;
cnt+=ceil((a[i]-c)/(1.0*b[i]));
}
}
return cnt<=mid;
}
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);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=2;i<=n;i++)scanf("%d",&b[i]);
ans=-1;
l=0;
r=a[1];
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
cout<<ans<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem J 异或的路径
https://ac.nowcoder.com/acm/contest/911/J
题意：给一棵 n 个点的树，1 号节点为根，边有边权，令 f(u,v) 表示 u 节点到 v 节点，路径上边权异或值。求 
题解：DFS+位运算
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,w;
ll ans,cnt,flag,temp,sum;
ll dis[N];
int vis[N];
int cct[N];
char str;
struct node{
int u,v,w;
node (){};
node(int u,int v,int w):u(u),v(v),w(w){}
};
vector<node>G[N];
void dfs(int u,int now){
dis[u]=now;
vis[u]=1;
int z=now;
int cnt=0;
while(z){
if(z&1)cct[cnt]++;
cnt++;
z>>=1;
}
for(int i=0,j=G[u].size();i<j;i++){
int v=G[u][i].v;
if(!vis[v]){
dfs(v,now^G[u][i].w);
}
}
}
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);
for(int i=2;i<=n;i++){
scanf("%d%d",&p,&v);
G[p].push_back({p,i,v});
G[i].push_back({i,p,v});
}
dfs(1,0);
for(int i=1;i<=n;i++){
for(int j=0;j<60;j++){
if((dis[i]>>j)&1)ans+=1ll*(1ll<<j)%MOD*(n-cct[j]);
else ans+=1ll*(1ll<<j)%MOD*cct[j];
ans%=MOD;
}
}
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 宝石序列
题意：
题解：
C++版本一
Problem L 最优子区间
题意：
题解：
C++版本一
