第五届新疆省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 节点，路径上边权异或值。求 结果对 1000000007 取模。

题解：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++版本一