[原创]2017广东工业大学程序设计竞赛决赛【解题报告】[补完√]

2017-03-26 23:00:02 Tabris_ 阅读数：2051

博客爬取于2020-06-14 22:41:06
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/66548177

先总结：
个人方面:审题不清，代码不稳。套路题过不掉。GG
比赛环境方面,判题慢到死,简直没法玩,做的最累的一套水题,如果能及时返回结果,对个人做题心态,感觉都会有提升的.

Problem A 两只老虎

————————————————————————————————————————————
首先考虑对于假如一只老虎只有两个耳朵或一个尾巴，那么总老虎数就是a/2+b，但是一共只有c/4个老虎，那么多出来的就是正常老虎的个数。即a/2+b-c/4

int main(){
    int _,a,b,c;
    scanf("%d",&_);
    while(_--){
        scanf("%d%d%d",&a,&b,&c);
        a/=2;c/=4;
        printf("%d\n",a+b-c);
    }
    return 0;
}

Problem B 占点游戏

————————————————————————————————————————————
比赛的时候理解错了题,以为是每轮两个人都走一格,然后看不懂样例,
目测就是两点的曼哈顿距离和N比较下，
如果两个人不能相遇，则 -1
能相遇那么结果就是1or2 讨论一下就好

瞎猜的没写代码。。等重现，，，

——————————————update————————————————

事实就是这样
考虑一个点能不能走到另一个点
如果能走到
—如果距离是奇数
------如果n是奇数那么先手多2
------如果n是偶数那么平
—如果距离是偶数
------如果n是奇数先手多1
------如果n是偶数后手多1
不能走到
—如果n是奇数先手多1
—如果n是偶数平

# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;

# define lowbit(x) (x&-x)
# define abs(x) ((x)>0?(x):-(x))

int main(){
    int _,n,x1,y1,x2,y2;
    scanf("%d",&_);
    while(_--){
        scanf("%d%d%d%d%d",&n,&x1,&y1,&x2,&y2);
        int dis = abs(x1-x2)+abs(y1-y2);
//        printf("%d  <--- \n",dis);
        if((n+1)/2>=dis){
            if(dis&1) {
                if(n&1) puts("2");
                else puts("-1");
            }
            else {
                puts("1");
            }
        }
        else {
            if(n&1) puts("1");
            else    puts("-1");
        }
    }
    return 0;
}

Problem C 爬楼梯

————————————————————————————————————————————
出烂了的题目,

f[i]=f[i-1]+f[i-2]+f[i-3];
代表转移个过程,

int f[200];
int main(){
    f[0]=1,f[1]=1,f[2]=2,f[3]=4;
    for(int i=4;i<=22;i++){
        f[i]=f[i-1]+f[i-2]+f[i-3];
        f[i]%=10007;
    }

    int _,n,x;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        int ans = 1;
        for(int i=1;i<n;i++){
            scanf("%d",&x);
            ans*=f[x];
            ans%=10007;
        }
        printf("%d\n",ans);
    }
    return 0;
}

Problem D 只有通过毁灭才能揭示真理

————————————————————————————————————————————
这个明白题意就能AC了

int main(){
    int _,a,b,c;
    scanf("%d",&_);
    while(_--){
        scanf("%d%d%d",&a,&b,&c);
        printf("%d\n",a*b+(a/30)*c);
    }
    return 0;
}

Problem E 倒水(Water)

————————————————————————————————————————————

其实这题贪心就好，
我们要最少的水杯，那就倍增的将若干个杯子变成一个就好了，
那么也就是说 $2^x$ 最后都能变成一个水杯, 这是不花费是最少的杯子个数
而我们要是最后的杯子个数<=k
那么只要最贪心的这个最小的两个 $2^x$ 变成一个就好了,
那么就是不断的加上最小的一个 $2^x$ ,最后能将这两个凑成一个

暴力写就好了时间上不会超过\logn的.

(其实就是一个树状数组更新的过程么。。

# define lowbit(x) (x&-x)

int a[N];
int cal(LL a){
    int num = 0;
    while(a){
        if(a&1) num++;
        a>>=1;
    }
    return num;
}
int main(){
    int _,k;
    LL n;
    scanf("%d",&_);
    while(_--){
        scanf("%lld",&n);
        scanf("%d",&k);
        LL ans = 0;
        while(cal(n)>k){
            ans+=lowbit(n);
            n+=lowbit(n);
        }

        printf("%lld\n",ans);
    }
    return 0;
}

Problem F tmk找三角

————————————————————————————————————————————
这题只知道要对树进行剖分,但是对于链上能不能构成三角形,我实在没有想到一个合适的复杂度来处理,

最后在他人的提示下才知道怎么处理,
先反过来想,一个序列里的数不能构成三角形,那么是fibo数列,没有问题,(详见2016CCPC长春签到题)
那么在 $10^9$ 的范围内fibo的长度也不超过50
那么也就是说如果数列的长度大于50 那么一定可以构成三角形,

所以对于大数据我们这样处理就好, 小数据就可以 $O(50)$ 处理就好了

个人用的是树剖,将边权转化为点权,
S->T路径上的所有点权处理一下就行了
(注意要去掉LCA(S,T)的点权

后来知道这是一个陈题,赛后在别处AC了一发

# include <bits/stdc++.h>
# define abs(x)   ((x)>0?(x):-(x))
typedef long long int LL ;
using namespace std;
const int N   = 100000+7;
const int MOD = 1000000007;
/*******************************************************/

int n,m;
int c[N];
vector<pair<int,int> >G[N];
void add(int u,int v,int w){
    G[u].push_back(make_pair(v,w));
    G[v].push_back(make_pair(u,w));
}
int fa[N],dep[N],sz[N],son[N];
void dfs1(int u,int f,int d){
    fa[u]=f,dep[u]=d,sz[u]=1,son[u]=0;
    int gz=G[u].size();
    for(int i=0,to;i<gz;i++){
        to=G[u][i].first;
        if(to==f) continue;
        c[to]=G[u][i].second;
        dfs1(to,u,d+1);
        sz[u]+=sz[to];
        if(sz[son[u]]<sz[to]) son[u]=to;
    }
}
int top[N],tree[N],pre[N],cnt;
void dfs2(int u,int tp){
    top[u]=tp,tree[u]=++cnt,pre[tree[u]]=u;
    if(son[u])dfs2(son[u],tp);
    int gz=G[u].size();
    for(int i=0,to;i<gz;i++){
        to=G[u][i].first;
        if(to==fa[u]||to==son[u]) continue;
        dfs2(to,to);
    }
}
int b[100];
void solve2(int x,int y,int lca){
    int fx=top[x],fy=top[y];
    int tot=0;
    while(fx!=fy){
        if(dep[fx]<dep[fy]) swap(fx,fy),swap(x,y);
//        printf("%d %d  <-----\n",x,fx);
        for(int i=tree[x];i>=tree[fx];i--){
//            printf("%d<-\n",i);
            if(pre[i]==lca) continue;
            b[tot++]=c[pre[i]];
        }
        x=fa[fx],fx=top[x];
    }
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=tree[x];i>=tree[y];i--){
        if(pre[i]==lca) continue;
        b[tot++]=c[pre[i]];
    }

    sort(b,b+tot);

//    for(int i=0;i<tot;i++) printf("%d ",b[i]);puts("");

    for(int i=2;i<tot;i++){
        if(b[i-1]+b[i-2]>b[i]){
            puts("Yes");
            return ;
        }
    }

    puts("No");
    return ;
}

void solve(int x,int y){
    int u=x,v=y;
    int fx=top[x],fy=top[y];
    int tot=0;
    while(fx!=fy){
        if(dep[fx]<dep[fy]) swap(fx,fy),swap(x,y);
        tot+=abs(tree[x]-tree[fx])+1;
        x=fa[fx],fx=top[x];
    }
    if(dep[x]<dep[y]) swap(x,y);
    tot+=abs(tree[x]-tree[y]);
    if(tot>=60) puts("Yes");
    else solve2(u,v,y);
    return ;
}

void init(){
    cnt = 0;c[1]=0;
    for(int i=1;i<=n;i++)    G[i].clear();
}

int main(){
    int _;
//    scanf("%d",&_);
    while(~scanf("%d",&n)){
        init();
        for(int i=2,u,v,w;i<=n;i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }

        dfs1(1,0,1);fa[1]=1;
        dfs2(1,1);

//        for(int i=1;i<=n;i++) printf("%d ",tree[i]);puts("");

        scanf("%d",&m);
        int u,v;
        while(m--){
            scanf("%d%d",&u,&v);
            solve(u,v);
        }
    }
    return 0;
}

Problem G 等凹数字

————————————————————————————————————————————
这道题最开始以为是一个数位dp,想在求区间回文数个数的代码上改一改 ,但是因为渣渣实在太菜,没有调出来,

快结束暴力处理了一下范围内所有等凹数字,发现只有180k+,
那么我们只要对区间进行二分就好了.

~~注:这题只是意念AC,等重现赛在提交一下~~ (已经AC)

后来看题解说数位DP也能过等下课回来补一个
(数位dp做法已更新在下面)

# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;
LL  sum;
LL a[500000],cnt;
int num[20],len;
void solve1(int n){
    if(n<10) return ;
    LL tem = n;len =0 ;
    num[len++]=n%10;
    n/=10;
    while(n){
        num[len++]=n%10;
        tem=tem*10+n%10;
        n/=10;
    }
    if(num[0]!=num[len-1])
    a[++cnt]=tem;
}
void solve2(int n){
    if(n<10) return ;
    LL tem = n;len = 0;
    while(n){
        num[len++]=n%10;
        tem=tem*10+n%10;
        n/=10;
    }
    if(num[0]!=num[len-1])
    a[++cnt]=tem;
}
void dfs(int s,int pre,int l,int n,bool state){
    if(s>=l) {
        if(state){
            solve1(n);
            solve2(n);
        }
        return ;
    }
    for(int i=pre;i>=0;i--){
        dfs(s+1,i,l,n*10+i,i<pre||state);
    }
}


LL cal(LL n){
    int l =1,r=cnt,mid,ans;
    while(l<=r){
        mid = (l+r)>>1;
        if(a[mid]>n) {
            r=mid-1;
        }
        else l=mid+1;
    }
    return r;
}
int main(){
    cnt = 0;
    for(int i=2;i<=9;i++)
        dfs(0,9,i,0,0);

//    printf("\n%lld\n",cnt);
    sort(a+1,a+cnt+1);
//    for(int i=1;i<=cnt;i++){
//        if(a[i]<=100000) sum++;
//        else break;
//        printf("%lld,",a[i]);
//    }
//    printf("%d\n",sum);
    int _,k;
    LL n,a,b;
    scanf("%d",&_);
    while(_--){
        scanf("%lld%lld",&a,&b);
        printf("%lld\n",cal(b)-cal(a-1));
    }
    return 0;
}

--------------Update--------------
数位dp是可解的

在基础的求回文数的数位dp上面多开两个维度,记录最高位的数字和前一位的数字即可

dp[最高位][当前位][前一位的数字][最高位的数字][可不可行(其实可以去掉这一维)]

dfs(最高位,当前位,前一位的数字,最高位的数字,数位限制,可不可行)

转移的时候只要考虑等凹数字的性质搜下去就行了对于不满足的可以不用搜

最开始并没有想到要记录最高位的数字这时候不记忆化也能能AC(因为数据水没有卡t)
最后在**Dei.**的提示下才写对鸣谢

# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;

int num[20],temp[20],len;
LL dp[20][20][10][10][2];

LL dfs(int pos,int cur,int pre,int fir,bool limit,bool state){
    if(cur<0) return state&&(pos>=2);
    if(!limit&&dp[pos][cur][pre][fir][state]!=-1)
        return dp[pos][cur][pre][fir][state];

    int endi = 9;
    if(limit) endi = num[cur];

    LL res = 0;
    for(int i=0;i<=endi;i++){
        temp[cur]=i;
        if(pos==cur&&0==i){
            res+=dfs(pos-1,cur-1,i,0,limit&&(i==endi),state);
        }
        else if(state&&cur<(pos+1)/2){
            if(temp[pos-cur]==i)
            res+=dfs(pos,cur-1,i,fir,limit&&(i==endi),temp[pos-cur]==i);
        }
        else if(state){
            if(pos!=cur&&i>pre) continue;
            if(i==temp[pos]&&cur==(pos+1)/2) continue;
                res+=dfs(pos,cur-1,i,temp[pos],limit&&(i==endi),state);
        }
    }

    if(!limit) dp[pos][cur][pre][fir][state]=res;
    return res;
}

LL solve(LL n){
    len = 0;
    while(n){
        num[len++]=n%10;
        n/=10;
    }
    return dfs(len-1,len-1,0,0,1,1);
}

int main(){
    memset(dp,-1,sizeof(dp));
    int _;
    LL l,r;
    scanf("%d",&_);
    while(_--){
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",solve(r)-solve(l-1));
    }
    return 0;
}

Problem H tmk买礼物

————————————————————————————————————————————
这道题被 Pending Rejudging了但绝对能AC

51nod上有一个加强版的题目题号1821

就是先升序排一下,在维护一个从0开始的变量,如果ans+1>=a[i] 的话就说明 $\big[0,ans+a[i]\big]$ 元素都能凑出来

处理一下就好了

int a[N];
int main(){
    int _,n;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        sort(a+1,a+n+1);
        LL ans = 0;
        for(int i=1;i<=n;i++){
            if(ans+1>=a[i]) ans+=a[i];
            else  break;
        }

        printf("%lld\n",ans);
    }
    return 0;
}