程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 【2016常州一中夏令營Day1】，2016常州day1

【2016常州一中夏令營Day1】，2016常州day1

編輯：C++入門知識

【2016常州一中夏令營Day1】，2016常州day1

Problem 1. suffix
給定一個單詞，如果該單詞以 er、 ly 或者 ing 後綴結尾，則刪除該後綴（題目保證刪除後綴後的單詞長度不為 0），否則不進行任何操作。
Input
輸入一行，包含一個單詞（單詞中間沒有空格，每個單詞最大長度為 32）
Output
輸出按照題目要求處理後的單詞。
Example
suffix.in suffix.out
referer refer
Scoring
• 對於 40% 的數據，單詞最大長度不超過 5。

題解

無可奉告

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int len;
char s[5005];

int main()
{
    int i,j;
    freopen("suffix.in","r",stdin);
    freopen("suffix.out","w",stdout);
    scanf("%s",s);
    len=strlen(s);
    if((s[len-1]=='r'&&s[len-2]=='e')||(s[len-1]=='y'&&s[len-2]=='l'))
    {
        for(i=0;i<=len-3;i++) printf("%c",s[i]);
        goto hhh;
    }
    if(s[len-1]=='g'&&s[len-2]=='n'&&s[len-3]=='i')
    {
        for(i=0;i<=len-4;i++) printf("%c",s[i]);
        goto hhh;
    }
    printf("%s",s);
    hhh:
    fclose(stdin);
    fclose(stdout);
    return 0;
    
}

Problem 2. weight
設有 1g, 2g, 3g, 5g, 10g, 20g 的砝碼各若干枚（其總重 ≤ 100, 000），要求：計算用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不用的情況。
Input
一行，包括六個正整數 a1, a2, a3, a4, a5, a6，表示 1g 砝碼有 a1 個， 2g 砝碼有 a2 個，……， 20g 砝碼有 a6 個。相鄰兩個整數之間用單個空格隔開。
Output
以“Total=N”的形式輸出，其中 N 為可以稱出的不同重量的個數。
Example
weight.in weight.out
1 1 0 0 0 0 Total=3
Explanation
樣例給出的砝碼可以稱出 1g, 2g, 3g 三種不同的重量。
Scoring
• 對於 20% 的數據，砝碼總個數不超過 20。
• 對於 40% 的數據，砝碼總個數不超過 800。

題解

二進制拆分+背包

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

int ans,cnt;
int a[7],w[200005],m[7]={0,1,2,3,5,10,20};
bool f[200005];
 
int main() 
{
    int i,j,t;
    freopen("weight.in","r",stdin);
    freopen("weight.out","w",stdout);
    for(i=1;i<=6;i++) 
    {
        scanf("%d",&a[i]);
        t=0;
        while(a[i]-(1<<t)>=0) 
        {
            a[i]=a[i]-(1<<t);
            w[++cnt]=m[i]*(1<<t);
            t++;
        }
        if(a[i]!=0) w[++cnt]=m[i]*a[i];
  
    }
    f[0]=1;
    for(i=1;i<=cnt;i++)
      for(j=100000;j>=1;j--)
        if(j-w[i]>=0) f[j]|=f[j-w[i]];

    for (i=1;i<=100000;i++) ans+=f[i];
    printf("Total=%d\n", ans);  
    return 0;
}

二進制拆分思想優化暴力也能過。

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

int tot,sum,now,pre,cnt;
int a[11],num[7]={0,1,2,3,5,10,20},n[100005];
bool u[100005];

bool check(int x)
{
    int i;
    for(i=7-x;i<=6;i++) 
        if(a[i]) return false;
    return true;
}
bool pd(int x)
{
    int i;
    for(i=1;i<=x;i++) 
        if(!a[i]) return false;
    return true;    
}
int main()
{
    int i,j,k,temp,beg,b,tt;
    bool flag;
    freopen("weight.in","r",stdin);
    freopen("weight.out","w",stdout);
    for(i=1;i<=6;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i]*num[i];
        if(a[i]) cnt++;
    }
    if(check(6-cnt))
    {
        tot=sum; 
        goto hhh;
    }
    for(i=1;i<=6;i++) 
        if(!pd(i)) {pre=i-1;break;}
    b=0;
    for(i=1;i<=6;i++) if(!a[i]) break;
    for(j=i;j<=6;j++) if(a[j]){b=j;break;}
    sum=0;
    for(i=1;i<=pre;i++) sum+=a[i]*num[i];
    for(i=1;i<=sum;i++)
    {
        n[i]=i;
        u[i]=true;
    }
    tot=sum;
    if(!b) goto hhh;
    for(i=b;i<=6;i++)
    if(a[i])
    {
        beg=tot;
        for(j=0;j<=beg;j++)
        {
            temp=n[j]+num[i]; 
            if(!u[temp])
            {
                u[temp]=true;
                n[++tot]=temp;
            }
        }
        tt=tot;
        for(k=2;k<=a[i];k++)
        {
            for(j=beg;j<=tt;j++)
            {
                temp=n[j]+num[i];
                if(!u[temp])
                {
                    u[temp]=true;
                    n[++tot]=temp;
                }
            }
             beg=tt;tt=tot;
        }
    }
    hhh:;
    printf("Total=%d",tot);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

Problem 3. hopscotch
給定一個 n 行 m 列的方格，每個格子裡有一個正整數 a， 1 ≤ a ≤ k, k ≤ n ∗ m
假設你當前時刻站在 (i, j) 這個格子裡，你想要移動到 (x, y)，那必須滿足以下三個條件
1： i < x
2： j < y
3：第 i 行第 j 列格子裡的數不等於第 x 行第 y 列格子裡的數
求從 (1, 1) 移動到 (n, m) 的不同的方案數
Input
第一行三個數 n, m, k
接下來 n 行每行 m 個正整數，表示每個格子裡的數
Output
一行一個數，表示從 (1, 1) 移動到 (n, m) 的不同的方案數，模 109 + 7
Example
hopscotch.in hopscotch.out
4 4 4 5
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1
Scoring
• 對於 20% 的數據， n, m ≤ 20。
• 對於 60% 的數據， n, m ≤ 100。
• 對於 100% 的數據， n, m ≤ 750。

題解 by TonyFang

http://tonyfang.is-programmer.com/posts/205063.html

首先我們用一個動態開點的權值線段樹的東西。

什麼是動態開點？

本來線段樹都是一開始build一下建完了，現在是邊插入邊建

由於線段樹插入一個數，其他的數的形態並不需要改變，所以就行啦。

大概insert的最重要的步驟如下（動態開節點）

if(! root) （還沒有開節點） root=++tot; （新開節點）

具體可以見代碼呀

這題dp是O(n^4)挺好想出來的，然後用減法原理變成一個類似於二維前綴和減去一些相等的dp值

那麼用動態開點權值線段樹就恰好能解決。時間復雜度O(n^2 logn)

//by TonyFang
# include <stdio.h>
# include <stdlib.h>
 
using namespace std;
 
int n, m, k;
long long f[760][760], s[760][760];
int a[760][760];
const int M=760*760*4, MOD = 1e9+7;
int lc[7000010], rc[7000010], num[7000010], root[M], tot=0;
 
inline void insert(int &rt, int l, int r, int pos, int val) {
    if(!rt) rt=++tot;
    if(l == r && l == pos) {
        num[rt] = num[rt] + val;
        num[rt] %= MOD; 
        return ;
    }
    int mid = l+r >> 1;
    if(pos <= mid) insert(lc[rt], l, mid, pos, val);
    else insert(rc[rt], mid+1, r, pos, val);
    num[rt] = num[lc[rt]] + num[rc[rt]];
    num[rt] %= MOD;
}
 
inline int query(int rt, int l, int r, int pos) {
    if(!rt) return 0;
    if(r <= pos) return num[rt];
    int mid = (l+r) >> 1, anss=0;
    if(lc[rt]) anss = (anss + query(lc[rt], l, mid, pos)) % MOD;
    if(rc[rt] && pos >= mid+1) anss = (anss + query(rc[rt], mid+1, r, pos)) % MOD;
    return anss;
}
 
int main() {
    freopen("hopscotch.in", "r", stdin);
    freopen("hopscotch.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=m; ++j) scanf("%d", &a[i][j]);
    f[1][1] = 1;
    for (int i=1; i<=n; ++i)
        s[1][i] = s[i][1] = 1;
    insert(root[a[1][1]], 1, m, 1, 1);
    for (int i=2; i<=n; ++i) {
        for (int j=2; j<=m; ++j) {
            f[i][j] = s[i-1][j-1];
            //printf("i=%d, j=%d\n", i, j);
            // sub
            int gg = query(root[a[i][j]], 1, m, j-1);
            //printf("i=%d, j=%d, s[i-1][j-1]=%d, sub=%d\n", i, j, s[i-1][j-1], gg);
            //printf("%d\n", gg);
            f[i][j] = ((f[i][j] - gg) % MOD + MOD) % MOD; 
            //printf("f[i][j]=%d\n",f[i][j]);
            s[i][j] = f[i][j];
            s[i][j] = (s[i][j] + s[i-1][j]) % MOD;
            s[i][j] = (s[i][j] + s[i][j-1]) % MOD;
            s[i][j] = ((s[i][j] - s[i-1][j-1]) % MOD + MOD) % MOD; 
        }
        for (int j=2; j<=m; ++j) 
            insert(root[a[i][j]], 1, m, j, f[i][j]);
    }
     
     
    printf("%d\n", f[n][m]);
    return 0;
}

Problem 4. alphabet
給定一棵 n 個點的樹，樹上每個節點代表一個小寫字母，詢問一個字符串 S 是否在樹上出現過？
字符串 S 出現過即表示存在兩個點 u, v， u 到 v 的最短路徑上依次連接所有點上的字母恰好是 S
Input
第一行一個數 T 表示數據組數
每組數據先輸入一個數 n 表示這棵樹有 n 個節點
接下來 n − 1 行每行兩個數 u, v，表示 u, v 之間存在一條無向邊
下一行包含 n 個字符，表示每個節點上的字符
下一行包含一個字符串 S
Output
對於每組數據”Case #k: ”， k 為測試點編號，如果出現過則輸出 Find，否則輸出 Impossible
Example
alphabet.in          alphabet.out
2                      Case #1: Find
7                      Case #2: Impossible
1 2
2 3
2 4
1 5
5 6
6 7
abcdefg
dbaefg
5
1 2
2 3
2 4
4 5
abcxy
yxbac
Scoring
• 對於 20% 的數據， N ≤ 1000。
• 對於另外 20% 的數據， N ≤ 104，且樹上有且僅有一種字母。
• 對於另外 30% 的數據， N ≤ 104，且樹隨機生成。
• 對於另外 30% 的數據， N ≤ 104，且樹上的字母隨機生成。

題解

統計起點和終點的個數，從個數少的開始暴力即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
 
int tt,n,cas,cnt,len;
int last[1000005];
char str[1000005],ask[1000005];
bool flag,ph[1005];
struct hh
{
    int next,to;
};
hh e[1000005];

void add(int a,int b) 
{
    ++cnt;
    e[cnt].to=b;
    e[cnt].next=last[a];
    last[a]=cnt;
}
 
void run(int x,int now) 
{
    int i,j;
    if(flag) return;
    if(now==len) 
    {
        flag=true;
        return;
    }
    for(i=last[x];i;i=e[i].next)
        if(str[e[i].to]==ask[now+1]) 
            run(e[i].to,now+1);
}
 
int main() 
{
    int i,j,a,b,s,t;
    freopen("alphabet.in","r",stdin);
    freopen("alphabet.out","w",stdout);
    scanf("%d",&tt);
    while(tt--) 
    {
        memset(last,0,sizeof(last));
        memset(ph,0,sizeof(ph));
        flag=false;cnt=0;
        scanf("%d",&n);
        for(i=1;i<=n-1;i++) 
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        scanf("%s",str+1);
        scanf("%s",ask+1);
        
        len=strlen(ask+1);
        for(i=1;i<=n;i++)  ph[str[i]]=true;
        for(i=1;i<=len;i++)
            if(!ph[ask[i]]) 
            {
                cas++;
                printf("Case #%d: Impossible\n",cas);
                goto hhh;
            }

        s=t=0;
        for(i=1;i<=n;i++) 
        {
            if(str[i]==ask[1]) s++;
            if(str[i]==ask[len]) t++;
        }
        if(s>t) reverse(ask+1,ask+len+1);

        for(i=1;i<=n;i++) 
            if(ask[1]==str[i]) 
            {
                run(i,1);
                if(flag) break;
            }
        cas++;
        if(flag) printf("Case #%d: Find\n",cas);
        else printf("Case #%d: Impossible\n",cas);
        hhh:;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

Problem 5. route
給一個 n ∗ m 的矩陣，矩陣的每個格子上有一個不超過 30 的非負整數。
我們定義一條合法的路線是從（ 1， 1）開始只能向右和向下移動到達（ n， m）的路線。
定義數列 A1, A2, A3, .., An+m−1 為一條合法路線上的序列，且 Aavg 為該數列的平均值。該路線的
價值為 (n + m − 1) 乘上該數列的方差。
即價值的表達式為 (n + m − 1) ∑n i=1 +m−1 (Ai − Aavg)2。
請找一條價值最小的路線，並輸出這個價值。
Input
第一行兩個正整數 n, m，表示矩陣的行數和列數。
以下 n 行每行 m 個非負整數 ai,j 表示矩陣上的數。
Output
包含一個整數，最小化的路線的價值。
Example
route.in route.out
2 2 14
1 2
3 4
Explanation
方案一： 1-3-4，平均數 Aavg = 8 3
方差 = (1 − 8 3)2 + (3 − 8 3)2 + (4 − 8 3)2 = 14 3
最終答案 = (2 + 2 − 1) ∗ 14 3 = 14
方案二： 1-2-4，平均數 Aavg = 7 3
方差 = (1 − 7 3)2 + (2 − 7 3)2 + (4 − 7 3)2 = 14 3
最終答案 = (2 + 2 − 1) ∗ 14 3 = 14
Scoring
• 對於 30% 的數據， n, m, ai,j ≤ 10。
• 對於 60% 的數據， n, m, ai,j ≤ 15。
• 對於 100% 的數據， n, m, ai,j ≤ 30。

題解

對於式子 $(n+m-1)*\sum_{i=1}^{n+m-1}(A_i-A_{avg})^2$

可拆開 $(n+m-1)*(\sum_{i=1}^{n+m-1}A_i^2-2*A_{avg}*\sum_{i=1}^{n+m-1}A_i+\sum_{i=1}^{n+m-1}A_{avg}^2)$

最後整理為 $(n+m-1)*\sum_{i=1}^{n+m-1}A_i^2-2*A_{sum}*\sum_{i=1}^{n+m-1}A_i+\sum_{i=1}^{n+m-1}A_{sum}^2$

$f[i][j][sum]$ 表示從 $(1,1)$ 走到 $(i,j)$ 和為 $sum$ 的最小值。

考慮優化空間，可枚舉 $sum$ ，不斷更新答案，於是 $f[i][j]$ 表示從 $(1,1)$ 走到 $(i,j)$ 的最小值。

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

int n,m,ans;
int a[55][55],f[55][55];
int main()
{
    int i,j,sum;
    freopen("route.in", "r", stdin);
    freopen("route.out", "w", stdout);
    ans=9999999;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(sum=0;sum<=(n+m-1)*30;sum++)
    {
        memset(f,0,sizeof(f));
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if(i==1) f[i][j]=f[i][j-1]; 
                else 
                    if(j==1) f[i][j]=f[i-1][j]; 
                    else f[i][j]=min(f[i-1][j],f[i][j-1]);
                f[i][j]+=a[i][j]*a[i][j]*(n+m-1)-2*a[i][j]*sum;
            }
        ans=min(ans,f[n][m]+sum*sum);
    }
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}