首页 > > 程序设计 > C/C++ >

【2016常州一中夏令营Day1】

2018-06-17 23:53:17来源：未知 阅读 ()

新老客户大回馈,云服务器低至5折

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;
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：【2016常州一中夏令营Day2】

下一篇：c++中stl容器的常用示例

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签