10.6 2023湖南省赛

2023湖南省赛

 A - 开开心心233

思路：点歌增加的歌曲数量可用等差求和公式求出，并且剩余的歌曲数量是单调的，可以二分求

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n,m;cin>>n>>m;
    int l=0,r=n,ans;
    auto check=[n,m](int x){
        int c=n-x;
        int sum=c*(c+1)/2-x;
        return sum<=m;
    };
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid))r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

F - 宝石交易

思路：可以有多种替换，那么对所有替换用图存后求Floyd；暴力遍历每个起点，求从该起点开始的最小花费

#include<bits/stdc++.h>
using namespace std;
int s[10010],t[10010];
int c[410][410];
#define INF 0x3f3f3f3f
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    for(int i=1;i<=n;i++){
        cin>>t[i];
    }
    for(int i=1;i<=400;++i)
        for(int j=1;j<=400;++j)
            c[i][j]=INF;
    for(int i=1;i<=m;i++){
        int a,b,r;
        cin>>a>>b>>r;
        //c[a][b]=r;
        c[a][b]=min(c[a][b],r);
    }
    for(int k=1;k<=400;++k)
        for(int i=1;i<=400;++i)
            for(int j=1;j<=400;++j)
                c[i][j]=min(c[i][k]+c[k][j],c[i][j]);
    int min1=INT32_MAX;
    for(int i=1;i<=n;i++){
        int f=0;
        int sum=0;
        for(int j=1;j<=n;j++){
            int d=t[(i+j-2)%n+1];//2
            int e=s[1+j-1];//1
            //cout<<d<<" "<<e<<endl;
            if(d==e)
                continue;
            if(c[d][e]==INF&&c[e][d]==INF){
                f=1;
                break;
            }
            else{
                sum+=min(c[d][e],c[e][d]);
            }
        }
        if(f==0){
            min1=min(min1,sum);
        }
    }
    if(min1!=INT32_MAX)
        cout<<min1<<endl;
    else
        cout<<-1<<"\n";
    return 0;
}

B - square game

思路：可以发现非平方数的sg，都等于距离最近的上一个平方数，那么所有数可以分成两种：n²，n²+1。用记忆化搜索求所有数的sg函数，异或和为非0则先手胜

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

vector<int>f(N);
int sg(int x){
    int y= ::sqrt(x),ed=y*y-y;
    if(y*y!=x)x=y*y+1,ed=y*y;
    if(f[x]!=-1)return f[x];
    unordered_set<int>se;
    for(int i=ed;i>=0;i-=y){
        se.insert(sg(i));
    }
    for(int i=0;i<N-4;++i){
        if(!se.count(i)){
            return f[x]=i;
        }
    }
}
void solve(){
    for(int i=1;i<N-4;++i)f[i]=-1;
    int n;cin>>n;
    int ans=0;
    for(int i=1,x;i<=n;++i){
        cin>>x;
        ans^=sg(x);
    }
    cout<<(ans?"First":"Second");
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}