玲珑杯 Round#18 C

【Topic Link】

1146 – 图论你先敲完模板

【题解】

首先我们可以想到一个简单的dp方程

dp[i]=min(dp[j]+2^(dis[i]−dis[j]))+a

1.然后我们发现这个如果dis[i]−dis[j]>30的时候,决策为从i到j分开走更划算.

所以我们可以从i-1往回(1)递推,如果某一点距离差大于30.则直接退出循环即可.

最终结果为dp[n].且结果需要用long long存.

【Source Code】
github: Round#18 C.cpp



#include<bits/stdc++.h>
#define fill(x) memset(x,0,sizeof(x))
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int maxn=100000+10;
int n;
long long dp[maxn],a,dt[100000+10];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%lld",&n,&a);
        for(int i=1;i<=n;++i){ 
            dp[i]=1000000000000000000; 
            scanf("%lld",&dt[i]); 
            for(int j=i-1;j>=1;--j){
                long long t;
                if(dt[i]-dt[j]>30)break;
                if(dp[j]!=1000000000000000000) t=dp[j];
                else t=0;
                dp[i]=min(dp[i],t+(1<<(dt[i]-dt[j]))+a);
            }
        }
        printf("%lld\n",dp[n]);
    }
    return 0;
}


玲珑杯 Round#18 A

【Topic Link】

1143 – 计算几何你瞎暴力

【题解】

用vis统计每个点上有多少教室.可以发现,最大的距离是30.

然后枚举所有的点求出两点之间的距离以及所有的组合总数.

1.如果两点是同一个点.先判断该点是否存在房子.如果存在,就用等差数列求和公式: N-1+N-2+…+1=(1+N-1)*(N-1)/2  计算出组合种数记录在d[0].

2.如果两点不同一点,判断两点教室数都不为0,然后计算组合种数: S*S2 计算组合种数记录在d[dist(S,S2)].

3.由于计算的时候每个点都在点一和点二计算过一次.所以最终统计的时候之前统计得值需要除以二.

【Source Code】

github: Round#18 A.cpp


#include<bits/stdc++.h>
#define cle(x) memset(x,0,sizeof(x))
#define INF 0x3f3f3f3f
using namespace std;

const int maxn=50000+10;
int T,n,q,d[1420];
char str[200];
long long vis[20][20][20];
bool vi[1420];

int main(){
    scanf("%d",&T);
    while(T--){
        cle(d),cle(vis),cle(vi);
        scanf("%d%d",&n,&q);
        for(int i=0;i<n;++i){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            vis[x][y][z]++;
        }
        for(int i=0;i<=10;i++)
        {
            for(int j=0;j<=10;j++)
            {
                for(int k=0;k<=10;k++)
                {
                    for(int x=0;x<=10;x++)
                    {
                        for(int y=0;y<=10;y++)
                        {
                            for(int z=0;z<=10;z++) { 
                                int dis=abs(i-x)+abs(j-y)+abs(k-z); 
                                if(i==x&&j==y&&k==z) { 
                                    if(vis[i][j][k]-1>=0){
                                        d[dis]+=(vis[i][j][k])*(vis[i][j][k]-1)/2;
                                        vi[dis]=true;
                                    }
                                }
                                else if(vis[i][j][k]*vis[x][y][z]>0)
                                {
                                    d[dis]+=vis[i][j][k]*vis[x][y][z];
                                    vi[dis]=true;
                                }
                            }
                        }
                    }
                }
            }
        }
        for(int i=1;i<=30;++i)d[i]=d[i-1]+d[i]/2;
        for(int i=0;i<q;++i){
            int R;
            scanf("%d",&R);
            R=min(30,R);
            printf("%lld\n",d[R]);
        }
    }
    return 0;
}

玲珑杯 R8 E

【Code】

签到题.

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

typedef long long LL;
LL sum[100010];
LL a[100010];
LL maxn[10000];
LL b[100010];
LL n,q,ca=1;

void solve(){
    char str;
    getchar();
    for(int i=1;i<=n;++i){
        str='\0';
        LL res;
        while(str!=' ' && str!='\n'){
            scanf("%c",&str);
            if((str==' ' || str=='\n') && !a[i]){ str='\0';continue;}
            if((str==' ' || str=='\n') && a[i])break;
            sum[i]+=(str-'0');
            res=a[i]*10+str-'0';
            a[i]=res;
        }
        if(maxn[sum[i]]){
            b[i]=maxn[sum[i]];
            if(maxn[sum[i]]<a[i])
                maxn[sum[i]]=a[i];
        }else{
            maxn[sum[i]]=a[i];
        }
    }
    while(q--){
        LL j;
        scanf("%lld",&j);
        if(b[j]>0 && j>0 && j<=n)
            printf("%lld\n",b[j]);
        else
            printf("-1\n");
    }
}

int main(){
    LL T;
    scanf("%d",&T);
    while(T--){
        memset(maxn,0,sizeof(maxn));
        memset(b,0,sizeof(maxn));
        memset(a,0,sizeof(maxn));
        memset(sum,0,sizeof(maxn));
        printf("Case #%d:\n",ca++);
        scanf("%lld %lld",&n,&q);
        solve();
    }
    return 0;
}

玲珑杯 R7 D-Pick Up Coin

【题解】

区间动态规划, dp[i,j]表示捡起 i~j 区间的硬币, 有:

dp[i,j] = max{ dp[i+1,k-1] + dp[k+1, j-1] + value[i] x value[k] x value[j] }
 

【Code】(不会,代码搁置,回头看)

#include<iostream>
#include<algorithm>
using namespace std;
int Q[1010];
int dp[1005][1005];
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    while(n--){
        int M;
        cin>>M;
        for(int i=1;i<=M;++i)
            cin>>Q[i];
        Q[0]=Q[M+1]=1;
        for(int i=0;i<=M+1;++i)
            for(int j=0;j<=M+1;++j)
                dp[i][j]=0;
        for(int len=1;len<=M;++len)
                for(int i=1,j=i+len-1;j<=M;++i,++j)
                    for(int k=i;k<=j;++k)
                        dp[i][j]=max(dp[i][j],dp[i][k-1]+dp[k+1][j]+Q[k]*Q[i-1]*Q[j+1]);

            cout<<dp[1][M]<<endl;
    }

    return 0;
}

玲珑杯 R7 C-Duplicate Numbers

problem:1073

用map维护.

#include<iostream>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int N;
    cin>>N;
    while(N--){
        int M,flag=0;
        cin>>M;
        map<int,int> ma;
        for(int i=0;i<M;++i){
            int n;
            cin>>n;
            ma[n]++;
            if(flag==0 && ma[n]>1) flag=1;
        }
        if(flag){
                map<int,int>::iterator it;
                for(it=ma.begin();it->second<=1;it++){}
                    cout<<it->first;
                    it++;
                for(;it!=ma.end();it++)
                    if(it->second>1)
                        cout<<" "<<it->first;
                cout<<endl;
        }else{
            cout<<"none"<<endl;
        }
    }

    return 0;
}