生活大爆炸版石頭剪刀布

題目描述

石頭剪刀布是常見的猜拳游戲：石頭勝剪刀，剪刀勝布，布勝石頭。如果兩個人出拳一樣，則不分勝負(fù)。在《生活大爆炸》第二季第8 集中出現(xiàn)了一種石頭剪刀布的升級版游戲。
升級版游戲在傳統(tǒng)的石頭剪刀布游戲的基礎(chǔ)上，增加了兩個新手勢：
斯波克：《星際迷航》主角之一。
蜥蜴人：《星際迷航》中的反面角色。
這五種手勢的勝負(fù)關(guān)系如表一所示，表中列出的是甲對乙的游戲結(jié)果。

現(xiàn)在，小A 和小B 嘗試玩這種升級版的猜拳游戲。已知他們的出拳都是有周期性規(guī)律的，但周期長度不一定相等。例如：如果小 A以“石頭 - 布- 石頭- 剪刀- 蜥蜴人- 斯波克”長度為6 的周期出拳，那么他的出拳序列就是“石頭- 布- 石頭- 剪刀- 蜥蜴人- 斯波克- 石頭- 布- 石頭- 剪刀- 蜥蜴人- 斯波克- ……”，而如果小B 以“剪刀- 石頭- 布- 斯波克- 蜥蜴人”長度為5 的周期出拳，那么他出拳的序列就是“剪刀- 石頭- 布- 斯波克- 蜥蜴人- 剪刀- 石頭- 布-斯波克- 蜥蜴人- ……”
已知小A 和小B 一共進(jìn)行N 次猜拳。每一次贏的人得1 分，輸?shù)牡? 分；平局兩人都得0 分?，F(xiàn)請你統(tǒng)計N 次猜拳結(jié)束之后兩人的得分。

輸入輸出格式

輸入格式：
輸入文件名為rps.in。
第一行包含三個整數(shù)：N ，NA，NB，分別表示共進(jìn)行 N 次猜拳、小 A 出拳的周期長度，小B 出拳的周期長度。數(shù)與數(shù)之間以一個空格分隔。
第二行包含NA個整數(shù)，表示小 A 出拳的規(guī)律，第三行包含NB個整數(shù)，表示小 B 出拳的規(guī)律。其中，0 表示“剪刀”，1 表示“石頭”，2 表示“布”，3 表示“蜥蜴人”， 4 表示“斯波克”。數(shù)與數(shù)之間以一個空格分隔。

輸出格式：
輸出文件名為**rps.out **。
輸出一行， 包含兩個整數(shù)，以一個空格分隔，分別表示小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%的數(shù)據(jù)，0 < N ≤ 200 ，0 < NA ≤ 200 ， 0 < NB ≤ 200 。

思路

用數(shù)組存下不同情況的貢獻(xiàn)(見代碼)
然后對每一個情況判斷

代碼

#include<cstdio>
using namespace std;
int n,na,nb,sa,sb,a[190],b[190],f[5][5];

void work() 
{
    for(int i=na;i<n;i++) a[i]=a[i%na]; 
    for(int i=nb;i<n;i++) b[i]=b[i%nb]; 
    f[0][2]=1,f[0][3]=1; 
    f[1][0]=1,f[1][3]=1;
    f[2][1]=1,f[2][4]=1;
    f[3][2]=1,f[3][4]=1;
    f[4][0]=1,f[4][1]=1;
}
void Input() //輸入 
{
    scanf("%d%d%d",&n,&na,&nb);
    for(int i=0;i<na;i++) scanf("%d",&a[i]);
    for(int i=0;i<nb;i++) scanf("%d",&b[i]);
}
int main()
{
    Input();
    work(); 
    for(int i=0;i<n;i++)
    sa+=f[a[i]][b[i]],sb+=f[b[i]][a[i]]; 
    printf("%d %d\n",sa,sb); 
    return 0;
}

無線網(wǎng)絡(luò)發(fā)射器選址

題目描述

隨著智能手機(jī)的日益普及，人們對無線網(wǎng)的需求日益增大。某城市決定對城市內(nèi)的公共場所覆蓋無線網(wǎng)。
假設(shè)該城市的布局為由嚴(yán)格平行的129 條東西向街道和129 條南北向街道所形成的網(wǎng)格狀，并且相鄰的平行街道之間的距離都是恒定值 1 。東西向街道從北到南依次編號為0,1,2…128 , 南北向街道從西到東依次編號為0,1,2…128 。
東西向街道和南北向街道相交形成路口，規(guī)定編號為x 的南北向街道和編號為y 的東西向街道形成的路口的坐標(biāo)是（x , y ）。 在 某 些 路口存在一定數(shù)量的公共場所 。
由于政府財政問題，只能安裝一個大型無線網(wǎng)絡(luò)發(fā)射器。該無線網(wǎng)絡(luò)發(fā)射器的傳播范圍
一個以該點(diǎn)為中心，邊長為2*d 的正方形。傳播范圍包括正方形邊界。
例如下圖是一個d = 1 的無線網(wǎng)絡(luò)發(fā)射器的覆蓋范圍示意圖。

現(xiàn)在政府有關(guān)部門準(zhǔn)備安裝一個傳播參數(shù)為d 的無線網(wǎng)絡(luò)發(fā)射器，希望你幫助他們在城市內(nèi)找出合適的安裝地點(diǎn)，使得覆蓋的公共場所最多。
輸入輸出格式
輸入格式：
輸入文件名為wireless.in。
第一行包含一個整數(shù)d ，表示無線網(wǎng)絡(luò)發(fā)射器的傳播距離。
第二行包含一個整數(shù)n ，表示有公共場所的路口數(shù)目。
接下來n 行，每行給出三個整數(shù)x , y , k , 中間用一個空格隔開，分別代表路口的坐標(biāo)( x , y )
以及該路口公共場所的數(shù)量。同一坐標(biāo)只會給出一次。

輸出格式：
輸出文件名為wireless.out 。
輸出一行，包含兩個整數(shù)，用一個空格隔開，分別表示能覆蓋最多公共場所的安裝地點(diǎn) 方案數(shù)，以及能覆蓋的最多公共場所的數(shù)量。

輸入輸出樣例
輸入樣例#1：

1  
2  
4 4 10  
6 6 20  

輸出樣例#1：

1 30

說明

對于100%的數(shù)據(jù)，1≤d≤20，1≤n≤20, 0≤x≤128,0≤y≤128,0<k≤1,000,000。

思路

對于每一個(x,y,k)，在(x-d~x+d , y-d~y+d)的坐標(biāo)中的ans都加上k;
表示在(x-d~x+d , y-d~y+d)的范圍內(nèi)放置路由器，都能覆蓋到(x,y)，
將他的值加上(x,y)處的公共場所數(shù)
最后循環(huán)找最大值。

代碼

#include<bits/stdc++.h>
using namespace std;
int d,a[129][129];
void fd(int x,int y,int z) {
    for (int i=-d; i<=d; i++)
        for (int j=-d; j<=d; j++)
          if (i+x>=0&&j+y>=0&&i+x<129&&j+y<129)
            a[x+i][y+j]+=z;
    return;
}
int main() 
{
    memset(a,0,sizeof(a));
    int x,y,n,z,ans=0,sum=0;
    scanf("%d%d",&d,&n);
    for (int i=1; i<=n; i++) {
        scanf("%d%d%d",&x,&y,&z);
        fd(x,y,z);
    }
    for (int i=0; i<=128; i++)
        for (int j=0; j<=128; j++) {
            if (a[i][j]==ans) 
                ++sum;
            if (a[i][j]>ans) {
                ans=a[i][j];
                sum=1;
            }
    }
    printf("%d %d",sum,ans);
    return 0;
}

聯(lián)合權(quán)值

題目描述

無向連通圖G 有n 個點(diǎn)，n - 1 條邊。點(diǎn)從1 到n 依次編號，編號為 i 的點(diǎn)的權(quán)值為W i ，每條邊的長度均為1 。圖上兩點(diǎn)( u , v ) 的距離定義為u 點(diǎn)到v 點(diǎn)的最短距離。對于圖G 上的點(diǎn)對( u, v) ，若它們的距離為2 ，則它們之間會產(chǎn)生Wu×Wv 的聯(lián)合權(quán)值。
請問圖G 上所有可產(chǎn)生聯(lián)合權(quán)值的有序點(diǎn)對中，聯(lián)合權(quán)值最大的是多少？所有聯(lián)合權(quán)值之和是多少？

輸入輸出格式

輸入格式：
輸入文件名為link .in。
第一行包含1 個整數(shù)n 。
接下來n - 1 行，每行包含 2 個用空格隔開的正整數(shù)u 、v ，表示編號為 u 和編號為v 的點(diǎn)之間有邊相連。
最后1 行，包含 n 個正整數(shù)，每兩個正整數(shù)之間用一個空格隔開，其中第 i 個整數(shù)表示圖G 上編號為i 的點(diǎn)的權(quán)值為W i 。

輸出格式：
輸出文件名為**link .out **。
輸出共1 行，包含2 個整數(shù)，之間用一個空格隔開，依次為圖G 上聯(lián)合權(quán)值的最大值和所有聯(lián)合權(quán)值之和。由于所有聯(lián)合權(quán)值之和可能很大，輸出它時要對10007 取余。

輸入輸出樣例

輸入樣例#1：

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

輸出樣例#1：

20 74

說明

對于30% 的數(shù)據(jù)，1 < n≤ 100 ；
對于60% 的數(shù)據(jù)，1 < n≤ 2000；
對于100%的數(shù)據(jù)，1 < n≤ 200 , 000 ，0 < wi≤ 10, 000 。

思路

枚舉每一個點(diǎn)；
然后枚舉可以連到他的點(diǎn)；
然后對著些點(diǎn)直接統(tǒng)計答案就好

代碼

#include<cstdio>
#include<iostream>
using namespace std;
const int N=2e5+5,mo=10007;
struct cs{int to,nxt;}a[N*2];
int head[N],ll,v[N];
int n,ans,x,y,maxans;
void init(int x,int y){
    a[++ll].to=y;
    a[ll].nxt=head[x];
    head[x]=ll;
}
void work(int x){
    int sum=0,ma=0,m=0;
    for(int k=head[x];k;k=a[k].nxt){
        if(v[a[k].to]>ma){
        m=ma;   
        ma=v[a[k].to];
        }else
        if(v[a[k].to]>m)m=v[a[k].to];
        ans=(ans+sum*v[a[k].to])%mo;
        sum=(sum+v[a[k].to])%mo;
    }
    maxans=max(maxans,ma*m);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        init(x,y); init(y,x);
    }
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)work(i);
    printf("%d %d",maxans,(ans*2)%mo);
}

尋找道路

題目描述

在有向圖G 中，每條邊的長度均為1 ，現(xiàn)給定起點(diǎn)和終點(diǎn)，請你在圖中找一條從起點(diǎn)到終點(diǎn)的路徑，該路徑滿足以下條件：
1 ．路徑上的所有點(diǎn)的出邊所指向的點(diǎn)都直接或間接與終點(diǎn)連通。
2 ．在滿足條件1 的情況下使路徑最短。
注意：圖G 中可能存在重邊和自環(huán)，題目保證終點(diǎn)沒有出邊。
請你輸出符合條件的路徑的長度。

輸入輸出格式

輸入格式：
輸入文件名為road .in。
第一行有兩個用一個空格隔開的整數(shù)n 和m ，表示圖有n 個點(diǎn)和m 條邊。
接下來的m 行每行2 個整數(shù)x 、y ，之間用一個空格隔開，表示有一條邊從點(diǎn)x 指向點(diǎn)y 。
最后一行有兩個用一個空格隔開的整數(shù)s 、t ，表示起點(diǎn)為s ，終點(diǎn)為t 。

輸出格式：
輸出文件名為**road .out **。
輸出只有一行，包含一個整數(shù)，表示滿足題目?述的最短路徑的長度。如果這樣的路徑不存在，輸出- 1 。

輸入輸出樣例
輸入樣例#1：

3 2  
1 2  
2 1  
1 3  

輸出樣例#1：

-1

輸入樣例#2：

6 6  
1 2  
1 3  
2 6  
2 5  
4 5  
3 4  
1 5  

輸出樣例#2：

3

說明

解釋1：

如上圖所示，箭頭表示有向道路，圓點(diǎn)表示城市。起點(diǎn)1 與終點(diǎn)3 不連通，所以滿足題
目描述的路徑不存在，故輸出- 1 。

解釋2：

如上圖所示，滿足條件的路徑為1 - >3- >4- >5。注意點(diǎn)2 不能在答案路徑中，因為點(diǎn)2連了一條邊到點(diǎn)6 ，而點(diǎn)6 不與終點(diǎn)5 連通。
數(shù)據(jù)范圍

對于30%的數(shù)據(jù)，0<n≤10，0<m≤20；
對于60%的數(shù)據(jù)，0<n≤100，0<m≤2000；
對于100%的數(shù)據(jù)，0<n≤10,000，0<m≤200,000，0<x，y，s，t≤n，x≠t。

思路

• 只需要在滿足條件上的點(diǎn)進(jìn)行最短路即可
• 那么這么找滿足條件的點(diǎn)呢,
• 先在循環(huán)中就標(biāo)記每個點(diǎn)的出度,
• 我們現(xiàn)在在終點(diǎn)進(jìn)行一次bfs,經(jīng)過一個點(diǎn)那么它的num數(shù)組++,也就是標(biāo)記一下它的入度,
• 那么spfa時滿足條件的點(diǎn)就是出度等于入度的點(diǎn)
  很簡單

代碼

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <queue>
using namespace std;
const int INF=100000111;
int n,m,s,t,tail,vis[350001],head1[350001],head2[350001],sign[350001],inqueue[350001],chu[350001],num[350001];
struct node {
    int u,v,next;
};
node r1[350001],r2[350001];
queue<int>q;
void add(int x,int y) {
    r1[++tail].u=x;
    r1[tail].v=y;
    r1[tail].next=head1[x];
    head1[x]=tail;
    r2[tail].u=y;
    r2[tail].v=x;
    r2[tail].next=head2[y];
    head2[y]=tail;
}
void bfs(int sx) {
    q.push(sx);
    sign[sx]=1;
    while (!q.empty()) {
        int sx=q.front();
        q.pop();
        for (int i=head2[sx];i;i=r2[i].next) {
            int nex=r2[i].v;
            num[nex]++; 
            if (!sign[nex]) {
                sign[nex]=1;
                q.push(nex);
            }
        }
    }
}
void spfa(int sx,int sy) {
    for (int i=1;i<=n;i++)
        vis[i]=INF;
    q.push(sx);
    inqueue[sx]=1;
    vis[sx]=0;
    while (!q.empty()) {
        int sx=q.front();
        q.pop();
        for (int i=head1[sx];i;i=r1[i].next) {
            int nex=r1[i].v;
            if (vis[sx]+1 < vis[nex] && num[nex]==chu[nex]) {
                vis[nex]=vis[sx]+1;
                if (!inqueue[nex]) {
                    inqueue[nex]=1;
                    q.push(nex);
                }
            }
        }
    }
    if (vis[sy] == INF) printf("-1"); 
    else printf("%d",vis[sy]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        chu[x]++;
    }
    scanf("%d%d",&s,&t);
    bfs(t);
    spfa(s,t);
    return 0;
}

飛揚(yáng)的小鳥

原題

Flappy Bird 是一款風(fēng)靡一時的休閑手機(jī)游戲。玩家需要不斷控制點(diǎn)擊手機(jī)屏幕的頻率來調(diào)節(jié)小鳥的飛行高度，讓小鳥順利通過畫面右方的管道縫隙。如果小鳥一不小心撞到了水管或者掉在地上的話，便宣告失敗。

• 為了簡化問題，我們對游戲規(guī)則進(jìn)行了簡化和改編:

游戲界面是一個長為 n，高為 m 的二維平面，其中有 k 個管道（忽略管道的寬度）。
小鳥始終在游戲界面內(nèi)移動。小鳥從游戲界面最左邊任意整數(shù)高度位置出發(fā)，到達(dá)游戲界面最右邊時，游戲完成。
小鳥每個單位時間沿橫坐標(biāo)方向右移的距離為 1，豎直移動的距離由玩家控制。如果點(diǎn)擊屏幕，小鳥就會上升一定高度 X，每個單位時間可以點(diǎn)擊多次，效果疊加；如果不點(diǎn)擊屏幕，小鳥就會下降一定高度 Y。小鳥位于橫坐標(biāo)方向不同位置時，上升的高度 X 和下降的高度 Y 可能互不相同。
小鳥高度等于 0 或者小鳥碰到管道時，游戲失敗。小鳥高度為 m 時，無法再上升。
現(xiàn)在,請你判斷是否可以完成游戲。如果可以，輸出最少點(diǎn)擊屏幕數(shù)；否則，輸出小鳥最多可以通過多少個管道縫隙。

輸入輸出

輸入格式

第 1 行有 3個整數(shù) n,m,，分別表示游戲界面的長度，高度和水管的數(shù)量，每兩個整數(shù)之間用一個空格隔開；

接下來的 nn 行，每行 2 個用一個空格隔開的整數(shù) X 和 Y，依次表示在橫坐標(biāo)位置 0～n?10～n?1 上玩家點(diǎn)擊屏幕后，小鳥在下一位置上升的高度 X，以及在這個位置上玩家不點(diǎn)擊屏幕時，小鳥在下一位置下降的高度 Y。

接下來 kk 行，每行 33 個整數(shù) P,L,HP,L,H，每兩個整數(shù)之間用一個空格隔開。每行表示一個管道，其中 PP 表示管道的橫坐標(biāo)，LL 表示此管道縫隙的下邊沿高度，HH 表示管道縫隙上邊沿的高度（輸入數(shù)據(jù)保證 PP 各不相同，但不保證按照大小順序給出）。

輸出格式

共兩行。

第一行，包含一個整數(shù)，如果可以成功完成游戲，則輸出 11，否則輸出 00。

第二行，包含一個整數(shù)，如果第一行為 11，則輸出成功完成游戲需要最少點(diǎn)擊屏幕數(shù)，否則，輸出小鳥最多可以通過多少個管道縫隙。

樣例一

input

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

output

1
6

樣例二

input

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

output

0
3

限制與約定

對于 30%的數(shù)據(jù)：5≤n≤10,5≤m≤10,k=05≤n≤10,5≤m≤10,k=0，保證存在一組> 最優(yōu)解使得同一單位時間最多點(diǎn)擊屏幕 33 次；
對于 50%的數(shù)據(jù)：5≤n≤20,5≤m≤105≤n≤20,5≤m≤10，保證存在一組最優(yōu)解使得同一單位時間最多點(diǎn)擊屏幕 33 次；
對于 70%的數(shù)據(jù)：5≤n≤1000,5≤m≤1005≤n≤1000,5≤m≤100；
對于 100%的數(shù)據(jù)：5≤n≤10000,5≤m≤1000，0≤k<n,0<X<m,0<Y<m,0<P<n,0≤L<H≤m,L+1<H5≤n≤10000,5≤m≤1000，0≤k<n,0<X<m,0<Y<m,0<P<n,0≤L<H≤m,L+1<H。

時間限制：1s1s
空間限制：128MB

說明

【輸入輸出樣例說明】
如下圖所示，藍(lán)色直線表示小鳥的飛行軌跡，紅色直線表示管道。

【數(shù)據(jù)范圍】
對于30% 的數(shù)據(jù)：5 ≤ n ≤ 10，5 ≤ m ≤ 10，k = 0 ，保證存在一組最優(yōu)解使得同一單位時間最多點(diǎn)擊屏幕3 次；
對于50% 的數(shù)據(jù)：5 ≤ n ≤ 2 0 ，5 ≤ m ≤ 10，保證存在一組最優(yōu)解使得同一單位時間最多點(diǎn)擊屏幕3 次；
對于70% 的數(shù)據(jù)：5 ≤ n ≤ 1000，5 ≤ m ≤ 1 0 0 ；
對于100%的數(shù)據(jù)：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 。

思路

首先想到設(shè)f[i][j]表示到第i行第j列所需要的最少點(diǎn)擊屏幕次數(shù)。轉(zhuǎn)移方程為

f[ i ][ j ]=min{f[ i-1 ][ j - k*x[i-1] ] + k} (1<= k <= j/x) 上升——①
f[ i ][ j ]=min{f[ i-1 ][ j + y[i-1] } ( j + y[i-1] <= m) 下降

顯然，下降可以O(shè)(1)轉(zhuǎn)移，主要問題在上升的轉(zhuǎn)移。

我們將上升的方程變一下：

f[ i ][ j - x[i-1] ]=min{f[ i-1 ][ (j - x[i-1]) - (k-1)*x[i-1] ] + k -1} ——②

這是 f[ i ][ j - x[i-1] ] 的轉(zhuǎn)移。

由 ② 化簡可得：

f[ i ][ j - x[i-1] ]=min{f[ i-1 ][ j - kx[ i-1] ] + k -1}——③
由①③消去f[ i-1 ][ j - kx[ i-1] ]+k可得
f[ i ][ j ]= f[ i ][ j - x[ i-1 ] ]+1

于是就可以O(shè)(n*m)的時間內(nèi)出解

代碼

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define rg register
using namespace std;
#define ll long long

inline int gi()
{
    rg bool b=0;
    rg int r=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-') b=!b;
        c=getchar();
    }
    while(c>='0' && c<='9')
    {
        r=r*10+c-'0';
        c=getchar();
    }
    if(b) return -r;
    return r;
}

const int inf = 2100000000, N = 10005, M = 1005;
int n,m,q,x[N],y[N],f[N][M];
bool b[N];
struct data
{
    int up,down;
} da[N];

int main()
{
    freopen ("birda.in","r",stdin);
    freopen ("birda.out","w",stdout);
    int i,p,j,k,cnt,ans;
    n=gi(), m=gi(), q=gi();
    for (i=0; i<n; i++) x[i]=gi(), y[i]=gi();
    for (i=1; i<=n; i++) da[i].down=0, da[i].up=m+1;
    for (i=0; i<q; i++) p=gi(), da[p].down=gi(), da[p].up=gi();    //一定要加，不然會影響到第65行的循環(huán)枚舉 
    for (i=1; i<=n; i++) for (j=0; j<=m; j++) f[i][j]=inf;    //初始化。0位置除地面外都為0
    f[0][0]=inf;
    for (i=1; i<=n; i++)
    {
        for (j=x[i-1]; j<=m; j++)
        {
            f[i][j]=min(f[i][j],f[i-1][j-x[i-1]]+1), f[i][j]=min(f[i][j],f[i][j-x[i-1]]+1);  //更新解，先不考慮水管 
            if (j == m)        //特殊判斷 j==m 的情況，因為不能超過 m ，所以有多種轉(zhuǎn)移 
                for (k=m-x[i-1]; k<=m; k++)
                    f[i][j]=min(f[i][j],f[i-1][k]+1), f[i][j]=min(f[i][j],f[i][k]+1);
        }
        for (j=da[i].down+1; j<da[i].up; j++)  //處理下落，必須是合法的 
            if (j+y[i-1] <= m)
                f[i][j]=min(f[i][j],f[i-1][j+y[i-1]]);
        for (j=1; j<=da[i].down; j++) f[i][j]=inf;  //考慮水管，去掉不合法的解 
        for (j=m; j>=da[i].up; j--) f[i][j]=inf;
    }
    cnt=q,ans=inf;
    for (i=n; i>=1; i--)
    {
        for (j=1; j<=m; j++) ans=min(ans,f[i][j]);  //若 ans 有值則代表能到達(dá)。 
        if (ans < inf) break;
        if (da[i].up <= m) cnt--;  //  da[i].up <= m 才是真水管 
    }
    if (cnt == q) printf("1\n%d\n",ans);
    else printf("0\n%d\n",cnt);
    return 0;
}

解方程

題目描述

已知多項式方程：

a0+a1x+a2x^2 +...+anx^n=00
求這個方程在[1, m ] 內(nèi)的整數(shù)解（n 和m 均為正整數(shù)）

輸入輸出格式

輸入格式：
輸入文件名為equation .in。

輸入共n + 2 行。
第一行包含2 個整數(shù)n 、m ，每兩個整數(shù)之間用一個空格隔開。
接下來的n+1 行每行包含一個整數(shù)，依次為a0,a1,a2..an

輸出格式：
輸出文件名為equation .out 。
第一行輸出方程在[1, m ] 內(nèi)的整數(shù)解的個數(shù)。
接下來每行一個整數(shù)，按照從小到大的順序依次輸出方程在[1, m ] 內(nèi)的一個整數(shù)解。

輸入輸出樣例

輸入樣例#1：

2 10 
1
-2
1

輸出樣例#1：

1
1

輸入樣例#2：

2 10
2
-3
1

輸出樣例#2：

2
1
2

說明

對于30%的數(shù)據(jù):0<n<=2,|ai|<=100,an!=0,m<100
對于50%的數(shù)據(jù):0<n<=100,|ai|<=10^100,an!=0,m<100
對于70%的數(shù)據(jù):0<n<=100,|ai|<=10^10000,an!=0,m<10000
對于100%的數(shù)據(jù):0<n<=100,|ai|<=10^10000,an!=0,m<1000000

思路

秦九韶算法
其實我們可以把左邊的式子當(dāng)成一個算式來計算，從1到m枚舉，只要結(jié)果是0，那么當(dāng)前枚舉到的值就是這個等式的解了?？梢酝ㄟ^編寫一個bool函數(shù)來判斷算式的值是不是0~

代碼

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int p=1000000007;//取模比較方便qwq為了出現(xiàn)奇怪的錯誤建議多模幾個質(zhì)數(shù) 
bool t=true;//用來判斷是否有解 
int n,m,ans,cnt,sum=0;//cnt記錄解的個數(shù)；sum用來計算多項式的結(jié)果 
int A[103],key[1000003];
//A[]記錄式中的a0,a1,a2(注意是以0為起點(diǎn))
//key記錄每個解的值 
ll read()//讀入優(yōu)化(似乎不加會T兩個點(diǎn)w) 
{
    ll sum=0,fg=1;
    char c=getchar();
    while(c < '0' || c > '9')
    {
        if(c=='-') fg=-1;//如果讀到負(fù)號則記錄 
        c=getchar();
    }
    while(c >='0' && c <='9')
    {
        sum=((sum*10)+c-'0')%p;
        //注意因為A[]可能很大，所以讀入時就要進(jìn)行取模操作 
        c=getchar();
    }
    return sum*fg;
    //如果是負(fù)數(shù)(fg==-1，即讀到了負(fù)號)那么返回的值為負(fù)數(shù) 
}
void print(int x)//輸出優(yōu)化(這個可以不加qwq) 
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        print(x/10);
    }
    putchar(x%10+'0');
}
bool calc(ll x)
{
    sum=0;//一定要清零！！！(不然只有10分嗚嗚嗚) 
    for(ll i=n;i>=0;i--)
    {
        sum=((A[i]+sum)*x)%p;
        //這里套用秦九韶算法求多項式的值 
    }
    return !sum;//如果答案是0說明x值為該多項式的解，返回1(true) 
}
int main()
{
    n=read();
    m=read();
    for(ll i=0;i<=n;i++)
    {
        A[i]=read();
    }
    for(ll i=1;i<=m;i++)
    {
        if(calc(i))//如果返回的是1(true)則說明有解 
        { 
            t=false; 
            ans++;//記錄答案個數(shù) 
            key[++cnt]=i;//記錄每個解的值 
        }
    }
    if(t)
    {
        cout<<ans<<endl;//如果t未改變則說明解的個數(shù)為0 
        return 0;
    }
    print(ans);
    printf("\n");
    for(ll i=1;i<=cnt;i++)
    {
        print(key[i]);
        printf("\n");
    }
    return 0;
}