天津大学程序设计竞赛 月赛 1

• 简单表达式求值
• 折绳子
• 弟弟的问题
• 船坞建造
• 印卡机

简单表达式求值

题目描述
天津大学（Tianjin University），简称天大，其前身为北洋大学，始建于1895年10月2日，是中国第一所现代大学，开中国近代高等教育之先河。tahara成功考上了天津大学，但是他收到了一份神秘邀请函，他需要将邀请函上的每步操作的返回值都得到才能获得录取通知书。邀请函上有两个数字n,m和m行代码，n代表变量x的初始值，每行代码均为“x++;”或"++x;"，tahara向你求助，希望你帮他成功拿到录取通知书。

输入
输入文件第一行包含两个整数n m，n为变量x的初始值，m为邀请函的代码行数,其中1<=n<=10^18,1<=m<=3000。
接下来的 m 行每行包括一行代码，代码只会出现“x++;”和"++x;"

输出
输出文件包含m行，包含m个整数，每个整数代表当前表达式的返回值。

样例输入 Copy
1895 2
++x;
x++;

样例输出 Copy
1896
1896

思路
就是签到题，注意一下输入要包括‘ ；’ ，还有就是n要开大一点。

#include<iostream>
#include<cstring>
using namespace std;

long long n;
char oper[3000][4];

int main()
{
    int m;
    cin >> n >> m;
    for(int i=0;i<m;i++)
        cin >> oper[i][0] >> oper[i][1] >> oper[i][2] >> oper[i][3];
    for(int i=0;i<m;i++)
    {
        if(oper[i][0]=='+'){
            n++;
            cout << n << endl;
        }else{
            cout << n << endl;
            n++;
        }
    }
    return 0;
}

折绳子

题目描述
tahara喜欢花花绿绿的绳子，这天捡到了一条绳子，长度为N，上面从左至右编号为0~N。
他想做一些操作，每次沿着绳子上的某个位置折叠，在进行完所有操作之后，最后的长度是多少。

输入
第一行两个数字N,M如题意所述。
接下来一行M个整数代表每次折叠的位置。

输出
一行一个整数代表答案。

样例输入 Copy
5 2
3 5

样例输出 Copy
2

提示
对于60%的数据，N,M ≤ 3000。
对于100%的数据，N ≤ 10^18,M ≤ 3000。
以编号为3的点折叠后，4号点和2号点重合，5号点和1号点重合，此时长度为3。
再以5号点为中心折叠，0号点和4号点重合，此时长度为2。

思路
为了方便求解，我们每次都在绳子折叠过后，将短的一半向长的一半折去，同时更新绳子的边界。可以理解为，每次折叠都舍去段的一半，因为绳子的长度只与长的一半有关，维护好边界数字就行。

#include<iostream>
#include<cstring>
using namespace std;

typedef unsigned long long ull;
ull N,M;
ull start,stop,lenstart,lenstop;
ull x[3010];

int main()
{
    memset(x,0,sizeof(0));
    cin >> N >> M;
    for(int i=0;i<M;i++)
        cin >> x[i];
    start=0;
    stop=N;
    for(int i=0;i<M;i++){
        lenstart=x[i]-start;//记录折叠过后两条绳子的长度
        lenstop=x[i]-stop;
        if(lenstart>lenstop){
            stop=x[i];//舍弃短边
            for(int j=i+1;j<M;j++)//更新后续折叠点不再范围内的点
                if(x[j]>stop)
                    x[j]=x[i]*2-x[j];
        }else{
            start=x[i];
            for(int j=i+1;j<M;j++)
                if(x[j]<start)
                    x[j]=x[i]*2-x[j];
        }
    }
    cout << stop-start << endl;
    return 0;
}

弟弟的问题

题目描述
tahara上了大学后，忘记了所有的功课。一天tahara的弟弟钾某人来问他一道数学题：
满足 A²-B²=C 的非负整数对(A,B) 有多少组。你能帮助tahara解答他弟弟的问题吗？

输入
输入数据包含多组测试实例，第一行输入一个整数T代表数据组数。
每组测试实例包含一行，包含一个整数C，1<=C<=1e9。
输出
对于每组输入数据，输出一行，为(a,b)的组数。

样例输入 Copy
1
7

样例输出 Copy
1

提示
只有一组(A, B), (4, 3) 满足 4 * 4 - 3 * 3 = 7。

思路
A²-B²=(A+B)(A-B)=C，只需要求以下满足条件的(A+B)和(A-B)，但要注意，因为A=[(A+B)+(A-B)]/2，B=[(A+B)-(A-B)]/2，很明显要求(A+B)和(A-B)要同奇偶，A和B才有对应的值。

#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;

void solve(int x)
{
    int cnt=0;
    int y=sqrt(x);
    for(int i=1;i<y;i++)
        if(x%i==0 && ((x/i)+i)%2==0)//判断数据是否符合条件
            cnt++;
    cout << cnt << endl;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x; 
        solve(x);
    }
    return 0;
}

船坞建造

题目描述
tahara有很多舰娘，为了让她们都能有足够的汽油，他把舰娘的家建在一条笔直的道路旁。tahara比较懒，为了省事儿他要搭建规模都相等的船坞，由于tahara有强迫症，他要给船坞放满船，所以每个船坞的舰娘数量都是相等的。每个船坞（除了第一个和最后一个）都直接和相邻的两个船坞相连接，一名舰娘一年要一吨汽油，tahara每年都会往船坞投放汽油，每个船坞获得的汽油数是不一样的。每个船坞获得的汽油既可以自己解决也可以运到其他船坞里，在运输过程中，每公里要上贡一吨汽油作为运费(但是一次运送多少吨都可以)。已知每个船坞这一年获得的汽油数，并假设运输方案是最佳的，计算tahara最多能养多少舰娘？

输入
输入文件第一行包含一个整数 N，1<=n<=1e5，表示船坞总数。
接下来的 N 行每行包括两个整数 a 和 b，其中 1<=a<=1e9，0<=b<=1e9，分别表示船坞的位置（坐标）和该船坞获得的汽油数，所有船坞按其位置从小到大排序给出，注意问题一定存在正整数解。

输出
输出文件仅一行，包含一个整数，表示每个船坞最多能养的舰娘的数量。

样例输入 Copy
4
20 300
40 400
340 700
360 600

样例输出 Copy
415

提示
样例解释:
位置20, 40, 340, 360的1,2,3,4号船坞，分别被发放了300, 400, 700, 600的汽油。
如果tahara把船坞的大小建成415。
此时，4号船坞先运输给3号船坞185吨石油，运送到3号船坞时石油只剩下了165。此时3号船坞可重新分配剩下的石油。
舰娘的个数必须为整数。

思路
贪心算法，只考虑当前点是否能够养活设定的舰娘数，多的借给下一个点，不够找下一个点借。加上二分的方法，提高效率。

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
ll x[100010][2];//x[i][0]用来记录位置,x[i][1]用来记录油量
ll Min=1,Max=1e9+1,Mid;
ll oil[100010];

int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> x[i][0] >> x[i][1];
    while(Min+1<Max)
    {
        Mid=(Min+Max)/2;
        for(int i=0;i<n;i++)
            oil[i]=x[i][1];
        for(int i=0;i<n-1;i++){
            if(oil[i]>Mid)//油量过剩，将油运给下一个点，但要保证能够运到
                oil[i+1]=oil[i+1]+max((ll)0,oil[i]-Mid-x[i+1][0]+x[i][0]);
            if(oil[i]<Mid)//油量不足，找下一个点借油
                oil[i+1]=oil[i+1]-x[i+1][0]+x[i][0]-Mid+oil[i];
        }
        if(oil[n-1]>=Mid)//油量有富余说明还可以养更多
            Min=Mid;
        else//油量不住说明应该少养
            Max=Mid;
    }
    cout << Min << endl;
    return 0;
}

印卡机

题目描述
tahara得到了一个印卡机，他想用印卡机得到卡片和小J进行黑暗游戏。印卡机的工作原理如下：设每张卡片的印的字符串为26个小写字母和符号“-”组成，向印卡机输入一个只由26个小写字母组成的字符串，印卡机可以将字符串中连续的部分子串用“-”变成缩略形式，比如串“ababcdefgab”，可以变成“aba-gab”,也可以变成"a-ba-gab",“zab"可以变成"z-ab”，这样就得到了一张卡片。tahara现在想知道自己可以印多少种类的卡。

印卡机有以下几个限制:

1. 缩写必须连续，即使"ab" 可以缩写，"ac"不可缩写。“za” 同样是看作连续
2. 对于已缩写的字符不可再改动， “abc” 不可缩写为 “a-b-c”
3. 对于字符串，可以进行多次缩写， 例如"abcd" 可以缩写为 “a-bc-d”
   输入
   输入数据包含多组测试实例，第一行输入一个整数T代表数据组数。
   每组测试实例包含一行，包含一个字符串s，s的长度不超过1e6。
   输出
   输出文件包含m行，包含m个整数，每个整数代表当前字符串可以生成的卡片种类。由于输出结果可能会很大， 结果需要对 1e9+7 取模。

样例输入 Copy
3
abc
zab
abca

样例输出 Copy
4
4
4

提示
abc纸带插入印卡机的输出可能为
abc, a-bc, ab-c, a-c
abca中，c-a不可执行缩写(不连续)，因此缩写方式也是4个。

思路
考虑每⼀段连续的点，如果缩写，其实是找两个点，⼀个作为开始，⼀个作为结束。此时很容易想到是
排列组合中的 ,但是其实还是可以选择多个缩写的，所以是⼀个排列组合的求和公式，即 C n 0 + C n 2 + C n 4 + C n 6 . . . . . . C_n^0+C_n^2+C_n^4+C_n^6...... Cn0​+Cn2​+Cn4​+Cn6​......，如果是奇数则最后加到 。由⼆项式的公式可以知道，求和的结果是2^n-1。

#include<iostream>
#include<cstring>
using namespace std;

const int mod=1e9+7;
const int MAX=1e5+1;
long long int spow[MAX];

int main()
{
    spow[0]=1;
    for(int i=1;i<MAX;i++)//用来计算每个不同长度的子串可以有多少种缩写
        spow[i]=spow[i-1]*2%mod;
    int n;
    cin >> n;
    while(n--){
        string x;
        cin >> x;
        int lenx=x.size();
        char cur;//记录上一个字符
        int len=0;
        bool flag=false;
        long long cnt=1;
        for(int i=0;i<lenx;i++){
            if(!flag){
                len=1;//开始新一轮的记录
                cur=x[i];
                flag=true;
            }else{
                if(x[i]-cur==1 || x[i]-cur==-25){
                    //正常的连续或者a和z的情况
                    len++;
                    cur=x[i];
                }else{
                    cnt=spow[len-1]*cnt%mod;
                    i--;
                    flag=false;
                }
            }
        }
        cnt=cnt*spow[len-1]%mod;
        cout << cnt << endl;
    }
    return 0;
}