您的位置: 首页  >  IT文章  >  【牛客---湖南大学2018年第十四届程序设计竞赛重现赛】

【牛客---湖南大学2018年第十四届程序设计竞赛重现赛】

分类: IT文章 • 2025-01-15 18:34:43

（第三次与中奖擦肩而过？

【A---A game】

题意：双人博弈：有N堆，每堆数量石子为M。给定K，每次可以把某一堆均分为石子数不小于K的几堆，（如果大于K，下次还可以用来分）。不可分的人输。

思路：不会。

【B：Jump】

题意：有N个人，每个人有两个数字xi和yi，选择其中一个可以使用，现在从1开始数，问最多能数到几。

思路：裸的二分图匹配。对于每个人（看成男生），向数字xi和yi（看成女生）分别连一条边。然后从女生开始吸匈牙利算法。

（ps：有傻瓜写二分+最大流了吗？N这么大，怕是不行额。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=2000010;
int Laxt[maxn],Next[maxn],To[maxn],cnt,N,M,T;
int linker[maxn],vis[maxn];
void add(int u,int v){
    Next[++cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
}
bool find(int u){
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(vis[v]!=T){
            vis[v]=T;
            if(!linker[v]||find(linker[v])){
                linker[v]=u; return true;
            }
        }
    }
    return false;
}
int main()
{
    int x,y,i,ans=0;
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
       scanf("%d%d",&x,&y);
       add(x,i); add(y,i);
    }
    for(i=1;i<=10000;i++){
        T=i;
        if(find(i)) ans++;
        else break;
    }
    cout<<ans<<endl;
    return 0;
}
View Code

【C：A+B】

裸的高精度加法。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
char a[maxn],b[maxn];
int A[maxn],B[maxn],C[maxn];
int main()
{
    int T,L1,L2,L3,i,j;
    scanf("%d",&T);
    while(T--){
        scanf("%s%s",a+1,b+1);
        L1=strlen(a+1);
        L2=strlen(b+1);
        L3=max(L1,L2)+2;
        for(i=L1;i>=1;i--) A[L1+1-i]=a[i]-'0';
        for(i=L1+1;i<=L3;i++) A[i]=0;
        for(i=L2;i>=1;i--) B[L2+1-i]=b[i]-'0';
        for(i=L2+1;i<=L3;i++) B[i]=0;
        for(i=1;i<=L3;i++) C[i]=A[i]+B[i];
        for(i=1;i<=L3;i++) C[i+1]+=C[i]/10,C[i]%=10;
        for(i=L3;i>1;i--) if(C[i]!=0) break;
        for(;i>=1;i--) cout<<C[i];
        cout<<endl;
    }
    return 0;
}
View Code

【D：Largest Circle】

题意：给定一个N凸多边形，问最大内接圆的半径。

思路：poj有原题，但是数据变大了（所以我直接抄代码T了。

（几何题，不会

【E：Let's brute force RSA】（拿了一血）

题意：除了题面长，每什么难度。题目以及给出了解法：就是给定N，找到两个素数p，q。满足p*q=N；然后得到L=(p-1)*(q-1)。然后找E关系L的逆元。

思路：扩欧求逆元。而用D=pow(E,L-2)是错的，因为E和L没有保证互质。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000000;
int p[maxn+10],vis[maxn+10],cnt;
void solve()
{
    for(int i=2;i<=maxn;i++){
        if(!vis[i]) p[++cnt]=i;
        for(int j=1;j<=cnt&&p[j]*i<=maxn;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
void extgcd(ll a,ll b,ll& d,ll& x,ll& y){ 
    if(!b){ d=a; x=1; y=0;} 
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); } 
} 
ll inverse(ll a,ll n){ 
    ll d,x,y; 
    extgcd(a,n,d,x,y); 
    return d==1?(x+n)%n:-1; 
} 
int main()
{
    solve();
    int T,i,j; ll E,D,N,pp,qq,L;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&E,&N);
        for(i=1;i<=cnt;i++){
            if(N%p[i]==0&&!vis[N/p[i]]){
                pp=p[i]; qq=N/p[i];
                break;
            }
        }
        L=(pp-1)*(qq-1);
        D=inverse(E,L);
        cout<<D<<" "<<N<<endl;
    }
    return 0;
}
View Code

【F：Similarity】（字符串，本来也是一血。。。emm，小失误）

题意：给定字符串S，T。求所有T的字串在S中出现的的次数和。

思路：后缀自动机求出S的每个字串以及拓扑得到每个字串的出现次数。然后T串在S上面跑。一直累加。

（比赛的时候错误原因是，在自动机上跑的时候没有模拟T串的长度。

（然后注意记忆话搜索或者加lazy。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn=1000010;
ll ans,dp[maxn]; char c[maxn];  
struct Sam
{
    int fa[maxn],ch[maxn][26],maxlen[maxn],Last,cnt;
    int a[maxn],b[maxn],num[maxn],np,nq,p,q;
    Sam(){ Last=cnt=1; }
    void add(int x)
    {
        np=++cnt; p=Last; Last=np;
        maxlen[np]=maxlen[p]+1; num[np]++; //方法1
        while(p&&!ch[p][x]) ch[p][x]=np,p=fa[p];
        if(!p) fa[np]=1;
        else {
            q=ch[p][x];
            if(maxlen[p]+1==maxlen[q]) fa[np]=q;
            else {
                nq=++cnt; maxlen[nq]=maxlen[p]+1;
                fa[nq]=fa[q]; fa[q]=fa[np]=nq;
                memcpy(ch[nq],ch[q],sizeof(ch[nq]));
                while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];
            }
        }
    }
    ll get(int tp)
    {
        if(tp<=1) return 0;
        if(dp[tp]) return dp[tp];
        dp[tp]=(ll)num[tp]*(maxlen[tp]-maxlen[fa[tp]]);
        dp[tp]+=get(fa[tp]);
        return dp[tp];
    }
    void sort()
    {
        for(int i=1;i<=cnt;i++) a[maxlen[i]]++;
        for(int i=1;i<=cnt;i++) a[i]+=a[i-1];
        for(int i=1;i<=cnt;i++) b[a[maxlen[i]]--]=i;  
        for(int i=cnt;i>=0;i--) num[fa[b[i]]]+=num[b[i]];
    }
    void solve()
    {
        scanf("%s",c+1); int L=strlen(c+1),Len=0; p=1; //记住模拟长度。。。
        for(int i=1;i<=L;i++){
            int x=c[i]-'a';
            if(ch[p][x]) Len++, p=ch[p][x];
            else {
                while(p&&!ch[p][x]) p=fa[p];
                if(!p) Len=0,p=1;
                else Len=maxlen[p]+1,p=ch[p][x];
            }
            int tp=p;
            ans+=(ll)(Len-maxlen[fa[tp]])*num[tp];  tp=fa[tp];
            ans+=get(tp);
        }
    }
}sam;
int main()
{
    scanf("%s",c+1); int L=strlen(c+1);
    for(int i=1;i<=L;i++) sam.add(c[i]-'a');
    sam.sort(); sam.solve();
    printf("%lld
",ans);
    return 0;
}
View Code

【I：Line K coverage】

题意：给定N个（N<30）居民点，每个点可以自己安装WIFI，价格是Wi，或者在某些点建立半径为R的WIFI发射器，价格是Ci，在发射器范围内的居民使用wifi不需要钱。现在最多可以建立K个WIFI发射器，问最小费用。

思路：DP做，dp[i][k]表示以i是最后一个发射器，前面i个居民点一共建立了k个发射器的最小花费。

 那么dp[i][k]=min(dp[j][k-1]+(j+1到i-1没有被j处的发射器和k处的发射器覆盖的居民点的安装WIFI的费用。)，...)

最后我们把每个dp[][]加上对于末尾没有覆盖到的费用，来更新答案。

（还未AC的代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=40;
const int inf=1e9+7;
struct in{ int x,w,c; }s[maxn];
bool cmp(in w,in v){ return w.x<v.x; }
int dp[maxn][maxn];
int cal(int bg,int ed,int L,int R)
{
    int res=0;
    for(int i=bg;i<=ed;i++) if(s[i].x>L&&s[i].x<R) res+=s[i].w;
    return res;
}
int main()
{
    int N,K,R,i,j,k,tmp;
    while(~scanf("%d%d%d",&N,&K,&R)){
       for(i=1;i<=N;i++) scanf("%d%d%d",&s[i].x,&s[i].w,&s[i].c);
       sort(s+1,s+N+1,cmp);
       K=min(N,K);
       for(i=1;i<=N;i++)
         for(j=1;j<=N;j++)
           dp[i][j]=inf;
       int ans=0; for(i=1;i<=N;i++) ans+=s[i].w;
       for(i=1;i<=N;i++){
          for(k=1;k<=i;k++) {
              if(k==1){
                  tmp=s[i].c+cal(1,i,-inf,s[i].x-R);
                 dp[i][k]=min(dp[i][k],tmp);
             }
              else { 
                 for(j=1;j<i;j++) {
                      tmp=s[i].c+dp[j][k-1]+cal(j+1,i,s[j].x+R,s[i].x-R);
                    dp[i][k]=min(dp[i][k],tmp); 
                 }
             }
          }
       } 
       for(i=1;i<=N;i++)
         for(k=1;k<=i;k++)
            ans=min(ans,dp[i][k]+cal(i+1,N,s[i].c+R,inf));
       printf("%d
",ans);
    }
    return 0;
}
View Code

【G：Max Convolution】

。。。

相关推荐