生存大爆炸版石头剪刀布

P1328 生活大爆炸版石头剪刀布

【标题叙述】

石头剪刀布是广泛的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。假诺五个人出拳一样,则不分胜负。在《生活大爆炸》第1季第七集中出现了一种石头剪刀布的进步版游戏。

晋级版游戏在守旧的石块剪子布游戏的底蕴上,扩大了三个新手势:

斯波克:《星际迷航》主角之一。

蜥蜴人:《星际迷航》中的反面剧中人物。

这三种手势的输赢关系如表一所示,表中列出的是甲对乙的游戏结果。

葡京手机登陆网址 1

现行反革命,小A 和小B
尝试玩那种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的,但周期长度不必然相等。例如:假设小
A以“石头 – 布- 石头- 剪刀- 蜥蜴人- 斯波克”长度为6
的周期出拳,那么她的出拳连串正是“石头- 布- 石头- 剪刀- 蜥蜴人- 斯波克-
石头- 布- 石头- 剪刀- 蜥蜴人- 斯波克- ……”,而一旦小B 以“剪刀- 石头- 布-
斯波克- 蜥蜴人”长度为5 的周期出拳,那么他出拳的行列正是“剪刀- 石头- 布-
斯波克- 蜥蜴人- 剪刀- 石头- 布-斯波克- 蜥蜴人- ……”

已知小A 和小B 一共实行N 次猜拳。每三遍赢的人得1 分,输的得0
分;平局三人都得0 分。现请你总括N 次猜拳结束之后多个人的得分。

【输入输出格式】

输入格式:

 

输入文件名为rps.in。

第1行李包裹罗两个整数:N ,NA,NB,分别代表共开始展览 N 次猜拳、小 A
出拳的周期长度,小B 出拳的周期长度。数与数以内以两个空格分隔。

第①行包蕴NA个整数,表示小 A 出拳的规律,第2行包括NB个整数,表示小 B
出拳的法则。其中,0 表示“剪刀”,1 代表“石头”,2 代表“布”,3
表示“蜥蜴人”, 4 表示“斯波克”。数与数以内以一个空格分隔。

 

输出格式:

 

出口文件名为rps.out 。

输出一行, 包蕴八个整数,以3个空格分隔,分别代表小A 、小B 的得分。

 

【输入输出样例】

输入样例#1:

10 5 6
0 1 2 3 4
0 3 4 2 1 0

输出样例#1:

6 2

输入样例#2:

9 5 5
0 1 2 3 4
1 0 3 2 4

出口样例#2:

4 4

【说明】

对于100%的数据,0 < N ≤ 200 ,0 < NA ≤ 200 , 0 < NB ≤ 200 。

葡京手机登陆网址 2葡京手机登陆网址 3

#include<iostream>
#include<cstdio>
using namespace std;
int n,n1,n2,map[10][10],a[210],b[210];
int main(){
    scanf("%d%d%d",&n,&n1,&n2);
    for(int i=1;i<=n1;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n2;i++)scanf("%d",&b[i]);
    for(int i=0;i<=4;i++)map[i][i]=0;
    map[0][2]=1;map[0][3]=1;map[1][3]=1;map[2][4]=1;map[3][4]=1;
    map[1][0]=1;map[2][1]=1;map[3][2]=1;map[4][0]=1;map[4][1]=1;
    int cnt1=0,cnt2=0,ans1=0,ans2=0;
    for(int i=1;i<=n;i++){
        cnt1++;cnt2++;
        if(cnt1>n1)cnt1=1;
        if(cnt2>n2)cnt2=1;
        ans1+=map[a[cnt1]][b[cnt2]];
        ans2+=map[b[cnt2]][a[cnt1]];
    }
    printf("%d %d",ans1,ans2);
}

100分 模拟

 

NOIp2014提高组

P1351 联合权值

【标题叙述】

无向过渡图G 有n 个点,n – 1 条边。点从1 到n 依次编号,编号为 i
的点的权值为W i ,每条边的长短均为1 。图上两点( u , v ) 的离开定义为u
点到v 点的最短距离。对于图G 上的点对( u, v) ,若它们的相距为2
,则它们中间会时有爆发Wu×Wv 的联合署名权值。

借问图G
上享有可发出一块权值的有序点对中,联合权值最大的是稍微?全体联合权值之和是稍微?

【输入输出格式】

输入格式:

 

输入文件名为link .in。

第③行包蕴1 个整数n 。

接下去n – 1 行,每行包括 2 个用空格隔开分离的正整数u 、v ,表示编号为 u
和数码为v 的点之间有边相连。

末尾1 行,包涵 n 个正整数,每四个正整数之间用1个空格隔断,当中第 i
个整数表示图G 上编号为i 的点的权值为W i 。

 

出口格式:

 

出口文件名为link .out 。

出口共1 行,包涵2 个整数,之间用二个空格隔绝,依次为图G
上联手权值的最大值

和兼具联合权值之和。由于全部联合权值之和恐怕十分的大,输出它时要对10007
取余。

 

【输入输出样例】

输入样例#1:

5  
1 2  
2 3
3 4  
4 5  
1 5 2 3 10 

输出样例#1:

20 74

葡京手机登陆网址 4

本例输入的图如上所示,距离为2 的有序点对有( 1,3) 、( 2,4) 、( 3,1) 、(
3,5) 、( 4,2) 、( 5,3) 。

其一起权值分别为2 、1⑤ 、2 、20、1五 、20。当中最大的是20,总和为74。

【数听闻明】

对于30% 的数据,1 < n≤ 100 ;

对于60% 的数据,1 < n≤ 2000;

对于100%的数据,1 < n≤ 200 , 000 ,0 < wi≤ 10, 000 。

葡京手机登陆网址 5葡京手机登陆网址 6

/*
    由于所给的图是一棵树,所以与某一点可以联合权值的点应该是它父亲节点的其他儿子节点,他的爷爷节点和他儿子的儿子节点,对于最终答案来说,某点的儿子的儿子节点和父亲的父亲节点可以算做一个
*/
#include<iostream>
#include<cstdio>
#define maxn 200010
#define mod 10007
#define LL long long
using namespace std;
int ans1,ans;
int n,num,head[maxn],fa1[maxn],fa2[maxn],w[maxn];
struct node{
    int to,pre;
}e[maxn*2];
void Insert(int from,int to){
    e[++num].to=to;
    e[num].pre=head[from];
    head[from]=num;
}
void dfs1(int father,int now){
    fa1[now]=father;fa2[now]=fa1[father];
    int t=w[now]*w[fa2[now]];
    ans1=max(ans1,t);
    ans=(ans+1LL*2*t%mod)%mod;
    for(int i=head[now];i;i=e[i].pre){
        int to=e[i].to;
        if(to==father)continue;

    }
}
int main(){
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        Insert(x,y);
        Insert(y,x);
    }
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    dfs1(0,1);
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=e[j].pre){
            int to1=e[j].to;
            for(int k=head[i];k;k=e[k].pre){
                int to2=e[k].to;
                if(to1==to2)continue;
                int t=w[to1]*w[to2];
                ans1=max(ans1,t);
                ans=(ans+t%mod)%mod;
            }
        }
    }
    cout<<ans1<<' '<<ans;
}

70分 暴力

葡京手机登陆网址 7葡京手机登陆网址 8

/*
        这个题取模特别容易出问题
        设sum[i]表示与点i直接相连的点权和
    可以发现,对于每个点i,它对联值权值之和的贡献=w[i]*sum[j] (j是与i直接相连的点)
    令maxn[i]表示与i直接相连的点中,最大的点权和
    那么对于i,最大的联合权值=w[i]*max(maxn[j])(j是与i直接相连的点)
    注意我们在计算最大的联合权值时,maxn[j]可能就是点i的权值,不合法
    所以同时记录maxn[j]是哪个点的点权,同时记录一个次大点权maxn_[j]
    统计答案时,枚举点i,枚举与i直接相连的点j,若maxn[j]对应得点=i,用次大点权来算
*/
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 200010
#define mod 10007
int num,head[maxn],n,w[maxn],m1[maxn],m2[maxn],mt[maxn];
long long ans1,sum[maxn];
int ans2;
struct node{
    int to,pre;
}e[maxn*2];
void Insert(int from,int to){
    e[++num].to=to;
    e[num].pre=head[from];
    head[from]=num;
}
int main(){
    //freopen("Cola.txt","r",stdin);
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        Insert(x,y);
        Insert(y,x);
    }
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=e[j].pre){
            int to=e[j].to;
            sum[i]=(sum[i]+w[to])%mod;
            if(w[to]>=m1[i]){
                m2[i]=m1[i];
                m1[i]=w[to];
                mt[i]=to;
            }
            else m2[i]=max(m2[i],w[to]);
        }
    }
    for(int i=1;i<=n;i++){
        int mx=0;
        for(int j=head[i];j;j=e[j].pre){
            int to=e[j].to;
            ans1=(ans1+(1LL*w[i]*(sum[to]-w[i]))%mod)%mod;
            int k=m1[to];
            if(mt[to]==i)k=m2[to];
            mx=max(k*w[i],mx);
        }
        ans2=max(ans2,mx);
    }
    cout<<ans2<<' '<<ans1;
}

100分

 

【标题叙述】

P一九四五 飞扬的小鸟

【标题叙述】

Flappy Bird是一款风靡目前的闲雅手提式有线电话机游戏。玩家须要持续控制点击掌提式有线电电话机显示屏的频率来调节小鸟的航空中度,让鸟儿顺遂经过画面右边的管道缝隙。固然小鸟一相当的大心撞到了水管只怕掉在地上的话,便发布破产。

为了简化问题,大家对游戏规则进行了简化和改编:

  1. 230日游界面是三个长为n ,高为 m 的二维平面,在那之中有k
    个管道(忽略管道的幅度)。

  2. 鸟儿始终在嬉戏界面内移动。小鸟从游戏界面最左侧任意整数中度地方出发,到达游戏界面最左侧时,游戏实现。

  3. 鸟儿各个单位时间沿横坐标方向右移的相距为1
    ,竖直移动的距离由玩家操纵。如若点击显示器,小鸟就会回升一定中度X
    ,各样单位时间足以点击多次,效果叠加;

假如不点击荧屏,小鸟就会回落自然中度Y
。小鸟位于横坐标方向不一样地点时,上升的莫斯中国科学技术大学学X 和降落的莫斯中国科学技术大学学Y 可能不尽相同。

  1. 鸟儿中度等于0 或然小鸟遭遇管道时,游戏退步。小鸟中度为 m
    时,不能再上涨。

方今,请你判定是或不是能够形成娱乐。倘若得以
,输出最少点击显示器数;不然,输出小鸟最多能够通过某个个管道缝隙。

【输入输出格式】

输入格式:

 

输入文件名为 bird.in 。

第二 行有3 个整数n ,m ,k
,分别代表游戏界面包车型大巴尺寸,中度和水管的多寡,每四个

平头之间用一个空格隔绝;

接下去的n 行,每行2 个用1个空格隔断的整数X 和Y ,依次表示在横坐标地点0
~n- 1

上玩家点击显示器后,小鸟在下一职位升起的可观X
,以及在那么些地点上玩家不点击荧屏时,

鸟类在下一职位下落的中度Y 。

接下去k 行,每行3 个整数P ,L ,H
,每多少个整数之间用三个空格隔开分离。每行表示一

个管道,其中P 表示管道的横坐标,L 表示此管道缝隙的下边沿高度为L ,H
代表管道缝隙

上边沿的中度(输入数据保障P 各区别,但不保证遵照轻重缓急顺序给出)。

 

出口格式:

 

出口文件名为bird.out 。

共两行。

首先行,包涵一个整数,假诺能够成功做到娱乐,则输出1 ,否则输出0 。

其次行,包括二个平头,借使第1行为1
,则输出成功达成娱乐要求最少点击显示屏数,不然,输出小鸟最多能够通过有个别个管道缝隙。

 

【输入输出样例】

输入样例#1:

10 10 6 
3 9  
9 9  
1 2  
1 3  
1 2  
1 1  
2 1  
2 1  
1 6  
2 2  
1 2 7 
5 1 5 
6 3 5 
7 5 8 
8 7 9 
9 1 3 

出口样例#1:

1
6

葡京手机登陆网址,输入样例#2:

10 10 4 
1 2  
3 1  
2 2  
1 8  
1 8  
3 2  
2 1  
2 1  
2 2  
1   2  
1 0 2 
6 7 9 
9 1 4 
3 8 10  

出口样例#2:

0
3

【输入输出样例表明】

如下图所示,深橙直线表示小鸟的宇宙航行轨道,青色直线表示管道。

葡京手机登陆网址 9

【数据范围】

对此三成 的数目:5 ≤ n ≤ 10,5 ≤ m ≤ 10,k = 0
,保障存在一组最优解使得一样单位时间最多点击显示器3 次;

对此5/10 的数量:5 ≤ n ≤ 2 0 ,5 ≤ m ≤
10,保障存在一组最优解使得一样单位时间最多点击显示器3 次;

对于70% 的数据:5 ≤ n ≤ 1000,5 ≤ m ≤ 1 0 0 ;

对于100%的数据:5 ≤ n ≤ 100 0 0 ,5 ≤ m ≤ 1 0 00,0 ≤ k < n ,0<X
< m ,0<Y <m,0<P <n,0 ≤ L < H ≤ m ,L +1< H 。

葡京手机登陆网址 10葡京手机登陆网址 11

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 10010
int n,m,cdt,ans=0x7fffffff,ans1;
bool flag,th[maxn];
struct node{
    int x,y;
}p[maxn];
struct Node{
    int l,h;
}c[maxn];
void dfs(int now,int hi,int cnt,int step){
    if(cnt>ans)return;
    if(now==n){
        ans=min(ans,cnt);
        flag=1;
        return;
    }
    ans1=max(ans1,step);
    if(hi-p[now].y<c[now+1].h&&hi-p[now].y>c[now+1].l){//说明可以不点击 
        if(th[now+1]){//下一秒要到达的地方有管道 
            dfs(now+1,hi-p[now].y,cnt,step+1);
        }
        else dfs(now+1,hi-p[now].y,cnt,step);
    }
    int sum=0;
    while(1){
        hi+=p[now].x;sum++;
        if(hi>m)hi=m;
        if(hi>=c[now+1].h)break;
        if(hi<=c[now+1].l)continue;
        if(th[now+1]){
            dfs(now+1,hi,cnt+sum,step+1);
        }
        else {
            dfs(now+1,hi,cnt+sum,step);
        }
        if(hi==m)return;
    }
}
int main(){
    //freopen("Cola.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&cdt);
    for(int i=0;i<=n;i++)c[i].l=0,c[i].h=m+1;
    for(int i=0;i<n;i++)scanf("%d%d",&p[i].x,&p[i].y);
    int u,v,w;
    for(int i=1;i<=cdt;i++){
        scanf("%d%d%d",&u,&v,&w);
        c[u].l=v;c[u].h=w;
        th[u]=1;
    }
    for(int i=1;i<=m;i++)dfs(0,i,0,0);
    if(flag){//能到达终点 
        printf("1\n");
        printf("%d",ans);
    }
    else {
        printf("0\n");
        printf("%d",ans1);
    }
}

50分 暴力

葡京手机登陆网址 12葡京手机登陆网址 13

/*
    50分做法:暴力dfs

    70分做法:
    向上的是完全背包,向下的是01背包
    令f[i][j]表示到达横坐标为i,高度为j的最小点击数
    向上的状态转移方程:f[i][j]=min( f[i-1][j-up[i-1]*k]+k )   k<=m/up[i-1]
    向下的状态转移方程:f[i][j]=min( f[i-1][j+down[i-1]]) 
    时间复杂度:O(nm2)

    100分做法:
    在向上的状态转移方程中,
    若p=j-up[i-1]*k, 那么到达状态p 和 到达状态j 的 很多起点是重复的
    也就是说,由重复的相同状态转移到了不同状态
    优化这个重复的相同状态
    假设一次上升高度x
        f[i][j-x]= min( f[i-1][ (j-x)-x*(k-1) ]+k-1 )
        原式:f[i][j]=min( f[i-1][j-x*k]+k)
    发现 当k>1时,f[i][j]=f[i][j-x]+1
    所以新的向上的状态转移方程:f[i][j]=min(f[i-1][j-x],f[i][j-x])+1
*/
#include<cstdio>
#include<algorithm>
#define N 10001
#define inf 20001
using namespace std;
int n,m,k,ok;
int up[N],down[N],top[N],bot[N];
int f[N][1001];
bool have[N];
int main() {
    scanf("%d%d%d",&n,&m,&k);
    int x;
    for(int i=0; i<n; i++) scanf("%d%d",&up[i],&down[i]);
    for(int i=1; i<=k; i++) {
        scanf("%d",&x);
        have[x]=true;
        scanf("%d%d",&bot[x],&top[x]);
    }
    for(int i=0; i<=n; i++)
        if(!top[i]) top[i]=m+1;
    for(int i=1; i<=n; i++)
        for(int j=0; j<=m; j++)
            f[i][j]=inf;
    //for(int i=0; i<=m; i++) f[0][i]=0;
    for(int i=0; i<=bot[0]; i++) f[0][i]=inf;
    for(int i=top[0]; i<=m; i++) f[0][i]=inf;
    for(int i=1; i<=n; i++) {
        for(int j=up[i-1]+1; j<=m; j++) f[i][j]=min(f[i-1][j-up[i-1]],f[i][j-up[i-1]])+1;
        for(int j=m-up[i-1]; j<=m; j++) f[i][m]=min(f[i][m],min(f[i][j],f[i-1][j])+1);
        for(int j=1; j<=m-down[i-1]; j++) f[i][j]=min(f[i][j],f[i-1][j+down[i-1]]);
        for(int j=0; j<=bot[i]; j++) f[i][j]=inf;
        for(int j=top[i]; j<=m; j++) f[i][j]=inf;
        if(!have[i]) continue;
        int j;
        for(j=bot[i]+1; j<=top[i]; j++)
            if(f[i][j]<inf) {
                ok++;
                break;
            }
        if(j>top[i]) {
            printf("0\n%d",ok);
            return 0;
        }
    }
    int sum=inf;
    for(int i=1; i<=m; i++) sum=min(sum,f[n][i]);
    printf("1\n%d",sum);
}

100分 dp

 

石头剪刀布是广阔的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。倘若多人出拳一样,则不分胜负。在《生活大爆炸》第①季第柒集中出现了一种石头剪刀布的晋级版游戏。
晋升版游戏在价值观的石块剪子布游戏的基础上,增加了七个新手势: 
斯波克:《星际迷航》主演之一。 
蜥蜴人:《星际迷航》中的反面剧中人物。 

这三种手势的成败关系如表一所示,表中列出的是甲对乙的游艺结果。

葡京手机登陆网址 14
今昔,小A 和小B
尝试玩那种升级版的猜拳游戏。已知他们的出拳都以有周期性规律的,但周期长度不肯定相等。例如:固然小
A以“石头 – 布- 石头- 剪刀- 蜥蜴人- 斯波克”长度为6
的周期出拳,那么他的出拳系列就是“石头- 布- 石头- 剪刀- 蜥蜴人- 斯波克-
石头- 布- 石头- 剪刀- 蜥蜴人- 斯波克- ……”,而倘诺小B 以“剪刀- 石头- 布-
斯波克- 蜥蜴人”长度为5 的周期出拳,那么他出拳的种类就是“剪刀- 石头- 布-
斯波克- 蜥蜴人- 剪刀- 石头- 布-斯波克- 蜥蜴人- ……”   

已知小A 和小B 一共展开N 次猜拳。每二回赢的人得1 分,输的得0
分;平局两个人都得0 分。现请你总括N 次猜拳截至现在五个人的得分。

【输入输出格式】

输入格式:

输入文件名为rps.in。 
先是行蕴涵八个整数:N ,NA,NB,分别表示共举行 N 次猜拳、小 A
出拳的周期长度,小B 出拳的周期长度。数与数里面以3个空格分隔。 
其次行包蕴NA个整数,表示小 A 出拳的原理,第①行包涵NB个整数,表示小 B
出拳的规律。在那之中,0 代表“剪刀”,1 表示“石头”,2 表示“布”,3
表示“蜥蜴人”,  4 意味“斯波克”。数与数里面以3个空格分隔。

出口格式:

输出文件名为rps.out 。 
出口一行,  包涵三个整数,以3个空格分隔,分别表示小A 、小B 的得分。

【输入输出样例】

输入样例#1:

10 5 6  
0 1 2 3 4 
0 3 4 2 1 0  

出口样例#1:

6 2

输入样例#2:

9 5 5 
0 1 2 3 4 
1 0 3 2 4 

出口样例#2:

4 4

【说明】

对于100%的数据,0 <  N  ≤   200 ,0 <  NA  ≤   200 ,  0
<  NB  ≤   200 。

【思路】

出于数据都十分小,此题用模拟的勤政算法既能够过,打1个表总括分裂拳种的景色,碰着景况进入判断即可。

const sco:array[0..4,0..4]of longint=(
(0,0,1,1,0),(1,0,0,1,0),(0,1,0,0,1),(0,0,1,0,1),(1,1,0,0,0)
);

var a,b:array[1..200]of longint;
    na,nb,la,lb,n,i:longint;

begin
    readln(n,la,lb);
    for i:=1 to la do read(a[i]);
    for i:=1 to lb do read(b[i]);
    for i:=1 to n do 
        begin
            inc(na,sco[a[((i-1) mod la)+1],b[((i-1) mod lb)+1]]);
            inc(nb,sco[b[((i-1) mod lb)+1],a[((i-1) mod la)+1]]);
        end;
    writeln(na,' ',nb);
end.