第十五届浙江大学宁波理工学院程序设计大赛（同步赛）_the 15th ningbo institute of technology, zju progr

链接：https://ac.nowcoder.com/acm/contest/303#question
来源：牛客网

目录（难题、不太会写的dp、未解决）

A.StarCraft          B.Fibonacci and Counting          C.LCPS          D.Campaign          

E.Build Pylons          F.Pylon Link          G.Rubik's Cube          H.Protoss and Zerg

I.Race Sorting          J.Carrier          K.Technology Tree          L.The Last Stand

---

卡在I上了，最后发现是c++的sort不稳定、、、、要死、=、=

 

A.StarCraft

星际争霸(StarCraft)作为暴雪游戏经典作品之一，在今年(2018年)迎来了20周年纪念。

tokitsukaze想知道，在哪年，星际争霸会迎来n周年纪念。

第一行输入一个正整数n(1≤n≤100)，表示n周年。
在一行输出一个正整数x，表示在x年，星际争霸会迎来n周年纪念。

签到题

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int c = 2018-20,n;
    cin>>n;
    cout<<c+n<<endl;
    return 0;
}

 

B.Fibonacci and Counting

我们这样定义斐波那契数列，F[1]=1,F[2]=1，当n>2时F[n]=F[n-1]+F[n-2]。

斐波那契数列的前10项为：1,1,2,3,5,8,13,21,34,55。

欧几里得算法求解两个数的最大公约数。我们记gcd(a,b)为整数a与b的最大公约数。

当b=0时，gcd(a,0)=a，否则gcd(a,b)=gcd(b,a%b)。其中%为取余运算。

在算法设计中，求解两个数字公约数的函数往往使用递归进行运算。

 

我们现在定义count(a,b)为a,b两个整数在使用欧几里得算法求解最大公因数时的递归次数。

 

例如count(4,8)=3，运算过程如下：

第一次调用gcd函数时进入gcd(4,8)，参数b不为0，所以递归进入gcd(8,4)。

进入gcd(8,4)为函数的第二次调用，参数b不为0，所以递归进入gcd(4,0)。

进入gcd(4,0)为函数的第三次调用，参数b=0。所以递归达到终点，停止递归。

在运算gcd(8,4)时共计进行了3次运算，所以count(8,4)=3。

现在给定一个正整数x，小w想要知道count(F(x),F(x+1))的值，你能告诉他么？

第一行输入一个正整数T(T≤1000)，表示有T组数据。
接下来T行，每行输入一个正整数x(1≤x≤1000000000)。

对于每组数据，依次输出一行一个正整数表示count(F(x),F(x+1))

f(x+1) = f(x)+f(x-1)，根据gcd，易知，下次递归是f(x-1)，f(x)，所以每次+1，（大胆猜也行）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;
    cin>>t;
    while(t--){
        ll x;
        cin>>x;
        cout<<x+1<<endl;
    }
    return 0;
}

C.LCPS

Given two strings,now you asked to tell the length of the Longest Common Palindrome Substring (LCPS) of them.

For example:

A = "abacabaqq"

B = "ccacaqaba"

So the LCPS is "aba" or "aca", and the length is 3.

 

But tokitsukaze think it's too simple to ask for the length.

tokitsukaze want you to tell the smallest lexicographical order one."aba" is smaller than "aca" , so the answer is "aba".

However , the output may very large.You just need to tell the index of answer in A and B.If the answer appears multiple times in A or B , you need tell the smallest one.(the index starts from 1.)

Now the answer is "aba".In string A , substring A[1..3]="aba" and A[5..7]="aba" .In string B , substring B[7..9]="aba".So you just output"1 3" and "7 9" in one line and print a blank between them.(s[i..j]=s[i]s[i+1]...s[j])

 

PS: Sorry for my poor English.

The first line of the input contains a single integer T(T≤40), indicating the number of test cases.

In each test case:
The first line of the input contains a single integer n(1≤n≤5*10^5), indicating the length of the string A and string B. (The length of A and B is equal)
The second line of the input contains a single string A(only contains 'a'-'z').
The third line of the input contains a single string B(only contains 'a'-'z').
It's guaranteed that the sum of n in all test cases will not exceed 2*10^6.

The first line of the output contains a single integer ,the length of the LCPS.
The second line of the output contains two integers L1 and R1,it means that in string A , substring A[L1..R1] is the answer.
The third line of the output contains two integers L2 and R2,it means that in string B , substring B[L2..R2] is the answer.
If A and B don't have LCPS , the answer is 0,and you don't need to print L1,R1,L2,R2.

 

D.Campaign

星际争霸(StarCraft)单人战役模式中有很多供人游玩的任务关卡。

tokitsukaze新开始了一关单人战役模式下的任务。在这场战役中，你要作为指挥官指挥克鲁普星区的艾伦人类(Terran)来防御人类的敌人——邪恶异虫(Zerg)的袭击。

这一次，作为指挥官，你的任务目标是尽可能多的保全人类方所拥有的7个基地。你在这次任务中拥有n个人口单位的兵力。为了防御异虫的攻击，每个基地都有一个能够抵挡异虫攻击的最小兵力需求L[i]，同时每个基地因为有固定的人口上限，分配给该基地的兵力也不得大于上限R[i]。

你需要在任务一开始就为这7个基地做好兵力分配，每个兵都应该分配给一个基地，即不应该有空闲兵力。如果任何一个基地被异虫攻破(分配的兵力大于0，且小于最小兵力需求，导致兵力白白葬送牺牲)，或者某个基地的人口超过了人口上限，兵力大于R[i]，任务都会直接失败。

为了避免任务失败，tokitsukaze决定从一开始就放弃一些基地(即不对这些基地派出兵力)。

请问保证任务成功的条件下，tokitsukaze最多留下多少个基地？特别的，如果任务失败这种情况下请输出"0"，不含引号。

由于tokitsukaze的星际操作十分流弊，你可以认为如果能够至少能够保留一个基地，任务就一定能够成功。

第一行输入一个T(T≤50000)，表示T组数据。
对于每组数据：
输入一个正整数n(1≤n≤10^9)表示需要分配的兵力总人口。
接下来7行，每行两个正整数L,R(1≤L≤R≤10^9),分别表示该基地够抵挡异虫攻击的最小兵力需求与该基地的人口上限。

对于每组数据，输出tokitsukaze最多能够留下几个基地，每组数据占一行。

暴力枚举每一种选择，然后判断是否n个人是否符合题意，也可以用二进制状态压缩（写起来更简单，也更直观）

///dfs
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll value[10][2],n;
int idx[8],deep,flag;
bool jude(int x){
    ll l = 0,r = 0;
    for(int i=0;i<x;i++){
        l += value[idx[i]][0];
        r += value[idx[i]][1];
    }
    return (l<=n)&&(n<=r);
}
void dfs(int t){
    if(t>=deep){
        if(jude(deep))
            flag = 1;
        return;
    }
    for(int i=!t?1:idx[t-1]+1;i<=7;i++){
        idx[t] = i;
        dfs(t+1);
    }
}
int sovle(){
    flag = 0;
    cin>>n;
    for(int i=1;i<=7;i++)
        cin>>value[i][0]>>value[i][1];
    for(deep = 7; deep ;deep--){
        dfs(0);
        if(flag)
            return 0*printf("%d\n",deep);
    }
    return 0*printf("0\n");
}
int main(){
    int t;
    cin>>t;
    while(t--)
        sovle();
    return 0;
}

///状压1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll value[10][2],n;
int idx[8],deep,flag;
void sovle(){
    flag = 0;
    cin>>n;
    for(int i=0;i<7;i++)
        cin>>value[i][0]>>value[i][1];
    int ans = 0;
    for(int i=0;i<(1<<7);i++){
        int x = i,cnt = 0;
        for(int j=0;j<7;j++)
            idx[j] = x%2,x/=2;
        ll l = 0,r = 0;
        for(int i=0;i<7;i++)
            if(idx[i]){
                l += value[i][0];
                r += value[i][1];
                cnt++;
            }
        if(l<=n && n<=r)
            ans = max(ans,cnt);
    }
    printf("%d\n",ans);
}
int main(){
    int t;
    cin>>t;
    while(t--)
        sovle();
    return 0;
}

///状压2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll value[10][2],n;
int idx[8],deep,flag;
void sovle(){
    flag = 0;
    cin>>n;
    for(int i=0;i<7;i++)
        cin>>value[i][0]>>value[i][1];
    ll ans = 0;
    for(int i=0;i<(1<<7);i++){
        ll l = 0,r = 0,cnt = 0;
        for(int j=0;j<7;j++)
            if(i&(1<<j)){
                l += value[j][0];
                r += value[j][1];
                cnt++;
            }
        if(l<=n && n<=r)
            ans = max(ans,cnt);
    }
    cout<<ans<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--)
        sovle();
    return 0;
}

 

E.Build Pylons

星际争霸(StarCraft)中，每个种族都有各自的基础单位，人族是宇宙建设车(SCV)，异虫是工蜂(Drone)，星灵是探机普罗比斯(Probe)，他们会建造建筑和采集资源，俗称农民。

SCV在开始执行建造命令后，到达指定地点后需要持续进行建造，直到SCV将建筑建造完成后才能执行下一个命令。

工蜂在开始执行建造命令后，到达指定地点后会自行开始一段时间的变异，变异结束后，将永久的失去这个工蜂，但建筑建造完成。

探机在开始执行建造命令后，只用在指定地点添加折跃(warp)空间标记，随后建筑将自行进行"折跃(warp)"，探机就可以去执行其他任务，经过一段的时间后，该建筑将自己完成"折跃"并可以使用，这时认为该建筑修建完毕。

因此，星灵建造建筑是最便捷的。

在星际争霸2中，有一种游戏模式是模式。合作模式中，有一种任务叫突变任务。突变任务指的是，在普通的合作任务下，增加了一些"突变因子"(额外的条件)，使得任务难度加大。每周的"突变因子"都不一样。

本周的"突变因子"，是给每个农民设定了一个疲劳属性，同时，你的所有建筑都只能建造在一个数轴上。

农民的疲劳值初始为0，每次该农民移动一个位置，消耗的时间为2*p+1秒，p表示当前疲劳值，在移动结束之后，疲劳值会增加1。当农民停下移动执行建造命令时，该农民的疲劳值会清0。

在本周的突变任务中，tokitsukaze控制着星灵单位。

tokitsukaze想要在一个基地的右侧建造n个水晶塔(Pylon)，水晶塔的折跃时间为k秒。

在这个突变任务里，她可以将一个农民部署在任何一个位置，这个农民每次可以向左或者向右移动1。如果该农民位于数轴坐标为x的位置，那么它每次可以移动到x-1或者x+1的位置(农民的初始疲劳值为0)。

现在给你tokitsukaze想要建造n个水晶塔的位置，请你安排一个合理的修建顺序，使得tokitsukaze建造完所有水晶塔的总时间最小（完成建造是指所有建造折跃完毕）。

第一行输入一个T(1≤T≤20)，表示有T组数据。
对于每组数据，第一行是两个正整数n,k(1≤n≤1000,1≤k≤10^5)，表示tokitsukaze想要建造n个水晶塔，并且每个水晶塔的折跃时间为k。
接下来一行n个用空格隔开的正整数pos[i](1≤pos[i]≤10000)，表示第i个水晶塔的位置为pos[i]。

对于每组数据，tokitsukaze建造所有建筑最少花费多少时间.

容易看出假设从1走到n，那么消耗是1,3,5,7，*****，2*n-1，求和是n*n，那么，也就是说

从一个地方到另一个地方的消耗是两个地方距离的平方，所以排个序，从小到大走一遍即可，最后别忘了加上k

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3+7;
ll pos[maxn],k,n;
ll o2(ll x){return x*x;}
void sovle(){
    ll ans = 0;
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>pos[i];
    sort(pos,pos+n);
    for(int i=0;i<n-1;i++)
        ans += o2(pos[i]-pos[i+1]);
    cout<<ans+k<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--)
        sovle();
    return 0;
}

 

F.Pylon Link

星灵(Protoss)有一个非常重要的建筑是水晶塔(Pylon)。

能量场(Energy Field)，是一个以水晶塔为圆心，半径为R的圆，R为正整数。所有的能量场的半径都是相同的。

星灵的绝大部分建筑都需要放置在能量场中。在星际争霸2(StarCraftⅡ)中，用折跃门(Warp Gate)折跃单位也需要放置在能量场中。如果水晶塔被破坏，那么能量场将消失，一些不在能量场范围内的建筑就会停止工作。所以水晶塔对于星灵来说，是一个十分重要的建筑。

tokitsukaze建造了n个水晶塔。她能够设定能量场的半径R。她想把每一个能量场都连接起来，使得单位(看成二维平面上的一个点)能从任意一个水晶塔出发，能到达所有的水晶塔，而且始终在能量场的范围内。她把这种状态，称为星灵的Link状态。

能量场连接的定义是：两个能量场相交或者相切。

tokitsukaze想知道，能量场的半径R至少为多少，能使星灵达到Link状态。

再次提醒：R为正整数。

第一行包含一个正整数T(T≤20)，表示T组数据。 对于每一组数据： 第一行包含一个正整数n(2≤n≤500)，表示有n个水晶塔。 接下来n行，每行两个整数x,y(-10^9≤x,y≤10^9)，表示这个水晶塔的坐标为(x,y)。数据保证没有两个水晶塔在同一个坐标。

对于每组数据，输出一个正整数，表示最小的R，能使星灵达到Link状态。

并查集+二分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    ll a,b;
}p[505];
int Fa[505],t,n;
void init(){for(int i=0;i<n;i++)Fa[i]=i;}
int Find(int x){return Fa[x]==x?x:Fa[x]=Find(Fa[x]);}
ll o2(ll x){return x*x;}
int Merge(int x,int y){
    x = Find(x),y = Find(y);
    if(x!=y)
        return Fa[y]=x,1;
    return 0;
}
bool chek(ll r){
    init();
    int cnt=0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            if((o2(p[i].a-p[j].a)+o2(p[i].b-p[j].b))/4<=r*r)
                cnt += Merge(i,j);
    return cnt==n-1;
}
void sovle(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>p[i].a>>p[i].b;
    ll l=1,r=1e10+1,mid,sul = 1;
    while(l<=r){
        mid=(r+l)/2;
        if(chek(mid))
            r=mid-1,sul = mid;
        else
            l=mid+1;
    }
    cout<<sul<<endl;
}
int main(){
    cin>>t;
    while(t--)
        sovle();
    return 0;
}

 

G.Rubik's Cube

小w一直在陪tokitsukaze玩星际，有一天他玩累了，他想找一些能够放松自己的事情做，比如玩玩魔方。这不是，小w就买了一个三阶魔方玩。（三阶魔方是3x3x3的标准魔方）

众所周知NIT集训队中有很多玩魔方的大佬，比如说doge和water，但是小w就不会玩魔方。小w买来一个数字魔方想要练习玩魔方的技巧。

魔方的每一个面可以看成是一个九宫格。

九宫格中每个位置都有一个0-9的数字。

因为小w不会玩魔方，所以他只能拼出一面。经过练习，他现在能够拼出一面中数字的和最大。

doge看到了他这么玩魔方，就想要考考他。

doge提出了m个问题，问小w能不能拼出某一面，使得这一面九宫格的数字之和等于某一个值。

如果小w能够做到的话请输出"Yes"否则请输出"No"(不含引号)。

第一行输入一个是一个正整数T(T≤10000)，表示有T组数据。

对于每组数据：

输入一个9行12列的字符型矩阵。

矩阵表示魔方的平面展开图，展开图的格式固定。

输入格式为:

***xxx******
***xxx******
***xxx******
xxxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxxx
***xxx******
***xxx******
***xxx******

表示一个魔方的平面展开图。

即：

"x"在输入的数据中是一个0-9的数字。并且对于每组数据，仅有"x"所代表的数字不同。

接下来输入一个正整数m(m≤100)表示有m组查询。

然后m行，每行一个整数queryx(0≤queryx≤81)，表示doge要求小w在魔方的某一面上拼出的数字和。

对于每一个查询，输出"Yes"或者"No"表示小w能否做到doge的要求。

大佬的思路好像是把魔方分成三种块，分别是一面二面三面的，然后开一个可达矩阵类似dp一顿操作，然后输出

咱稍微改了下，适合咱的风格

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using namespace std;
int t,q,x;
char mf[15][15];
struct node1{
    int a,b;
}n1[15];
struct node2{
    int a,b,c;
}n2[15];
struct node3{
    int a;
}n3[15];
bool can[90][10];
inline void one(){
    n3[1]=node3{mf[1][4 ]-'0'};
    n3[2]=node3{mf[4][1 ]-'0'};
    n3[3]=node3{mf[4][4 ]-'0'};
    n3[4]=node3{mf[4][7 ]-'0'};
    n3[5]=node3{mf[4][10]-'0'};
    n3[6]=node3{mf[7][4 ]-'0'};
}
inline void two(){
    n1[1 ]=node1{mf[0][4 ]-'0',mf[3][10]-'0'};
    n1[2 ]=node1{mf[1][3 ]-'0',mf[3][1 ]-'0'};
    n1[3 ]=node1{mf[1][5 ]-'0',mf[3][7 ]-'0'};
    n1[4 ]=node1{mf[2][4 ]-'0',mf[3][4 ]-'0'};
    n1[5 ]=node1{mf[4][0 ]-'0',mf[4][11]-'0'};
    n1[6 ]=node1{mf[4][2 ]-'0',mf[4][3 ]-'0'};
    n1[7 ]=node1{mf[4][5 ]-'0',mf[4][6 ]-'0'};
    n1[8 ]=node1{mf[4][8 ]-'0',mf[4][9 ]-'0'};
    n1[9 ]=node1{mf[5][1 ]-'0',mf[7][3 ]-'0'};
    n1[10]=node1{mf[5][4 ]-'0',mf[6][4 ]-'0'};
    n1[11]=node1{mf[5][7 ]-'0',mf[7][5 ]-'0'};
    n1[12]=node1{mf[5][10]-'0',mf[8][4 ]-'0'};
}
inline void three(){
    n2[1]=node2{mf[0][3]-'0',mf[3][0]-'0',mf[3][11]-'0'};
    n2[2]=node2{mf[0][5]-'0',mf[3][8]-'0',mf[3][9 ]-'0'};
    n2[3]=node2{mf[2][3]-'0',mf[3][2]-'0',mf[3][3 ]-'0'};
    n2[4]=node2{mf[2][5]-'0',mf[3][5]-'0',mf[3][6 ]-'0'};
    n2[5]=node2{mf[8][3]-'0',mf[5][0]-'0',mf[5][11]-'0'};
    n2[6]=node2{mf[8][5]-'0',mf[5][8]-'0',mf[5][9 ]-'0'};
    n2[7]=node2{mf[6][3]-'0',mf[5][2]-'0',mf[5][3 ]-'0'};
    n2[8]=node2{mf[6][5]-'0',mf[5][5]-'0',mf[5][6 ]-'0'};
}
void sovle(){
    memset(can,false,sizeof(can));
    can[0][0]=true;
    //for(int i=0;i<9;i++) cin>>mf[i];
    for(int i=0;i<9;i++)scanf("%s",mf[i]);
    two();
    for(int i=1;i<=12;i++){///一共十二个两面的角
        for(int j=4;j>=1;j--){///一面有四个两面的角
            for(int k=81;k>=0;k--){///最大81
                if(k>=n1[i].a) can[k][j] |= can[k-n1[i].a][j-1];
                if(k>=n1[i].b) can[k][j] |= can[k-n1[i].b][j-1];
            }
        }
    }
    three();
    for(int i=1;i<=8;i++){///一共八个三面的角
        for(int j=8;j>=5;j--){///一面有四个三面的角
            for(int k=81;k>=0;k--){
                if(k>=n2[i].a) can[k][j] |= can[k-n2[i].a][j-1];
                if(k>=n2[i].b) can[k][j] |= can[k-n2[i].b][j-1];
                if(k>=n2[i].c) can[k][j] |= can[k-n2[i].c][j-1];
            }
        }
    }
    one();
    for(int i=1;i<=6;i++){///一共六个三面的角
        for(int k=81;k>=0;k--){
            if(k>=n3[i].a)
                can[k][9] |= can[k-n3[i].a][8];
        }
    }
    //cin>>q;
    scanf("%d",&q);
    while(q--){
        //cin>>x;
        scanf("%d",&x);
        printf("%s\n",can[x][9]?"Yes":"No");
        //cout<<(can[x][9]?"Yes":"No")<<endl;
    }
}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(NULL),cout.tie(NULL);
    scanf("%d",&t);
    while(t--)
        sovle();
    return 0;
}

 

 

H.Protoss and Zerg

1v1，是星际争霸(StarCraft)中最常见的竞技模式。

tokitsukaze进行了n场1v1。在每一场的1v1中，她都有星灵(Protoss)和异虫(Zerg)两个种族可以选择，分别有a个单位和b个单位。因为tokitsukaze不太擅长玩人类(Terran)，所以她肯定不会选择人类。

对于每一场1v1，玩家只能控制己方单位。也就是说，如果选择虫族，那么只能控制虫族单位，如果玩家选择星灵，那么只能控制星灵单位。

在n场1v1中，假设第i场，有ai个虫族单位，和bi个星灵单位。tokitsukaze可以在一场1v1中，任选一种种族进行游戏。如果选择了虫族，那么在这场游戏中，可以选择出兵1到ai个单位。那么同理，如果选择了星灵，那么在这场游戏中，可以选择出兵1到bi个单位。

假设所有异虫单位互不相同，所有星灵单位也互不相同，那么请问tokitsukaze打完这n场1v1，出兵的总方案数是多少，由于答案很大，所以输出答案mod 998244353 后的结果。

注意：若两个方案，有其中一个单位不同，即视为不相同。

第一行包含一个T(T≤10)，表示T组数据。
对于每组数据：
第一行包含一个正整数n(1≤n≤100000)。
接下来n行，第i行包含两个整数ai,bi(1≤ai,bi≤10^9)，表示第i场1v1，有ai个异虫单位，和bi个星灵单位。

对于每组数据，输出一行，表示mod 998244353后的答案。

说明：
第一组样例：
对于第一场对局，tokitsukaze可以选择的虫族兵种有一个，并且将其编号为1，tokitsukaze可以选择的星灵兵种有两个，将其编号为1,2。所以tokitsukaze有四种可供选择的游戏方案：
1、选择虫族，并且派出虫族1号兵种。
2、选择星灵族，并且派出星灵族1号兵种。
3、选择星灵族，并且派出星灵族2号兵种。
4、选择星灵族，并且派出星灵族1，2号兵种。
对于第二场对局，tokitsukaze可以选择的虫族兵种有两个，并且将其编号为1,2，tokitsukaze可以选择的星灵兵种有一个，将其编号为1。所以tokitsukaze有四种可供选择的游戏方案：
1、选择虫族，并且派出虫族1号兵种。
2、选择虫族，并且派出虫族2号兵种。
3、选择虫族，并且派出虫族1，2号兵种。
4、选择星灵族，并且派出星灵族1号兵种。
两场对局是相互独立的事件，所以两轮游戏的出兵方案总数为4*4(mod 998244353)=16种。

从说明中容易看出来，快速幂取模即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p = 998244353;
ll Pow(ll a,ll b){
    a %= p;
    ll ans = 1;
    while(b){
        if(b&1)
            ans = ans*a%p;
        a = a*a%p;
        b>>=1;
    }
    return ans;
}
int main(){
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        ll ans = 1,a,b;
        while(n--){
            cin>>a>>b;
            ans = ans*((Pow(2ll,a)-1+p)%p+(Pow(2ll,b)-1+p)%p)%p;
        }
        cout<<ans%p<<endl;
    }
    return 0;
}

 

I.Race Sorting

星际争霸(StarCraft)是暴雪公司制作发行的一款即时战略游戏。游戏描述了26世纪初期，位于银河系中心的三个种族在克普鲁星际空间中争夺霸权的故事。三个种族分别是：人类(Terran)，异虫(Zerg)，星灵(Protoss)。

现在tokitsukaze拥有n个单位，每个单位的编号是1-n，且没有任何两个单位编号相同。每个单位可能是人类，异虫，星灵中的一种。

tokitsukaze定义了一种排序：种族排序(Race Sorting)。

规则是这样的：规定三个种族的先后顺序，race1,race2,race3，表示第一个种族的所有单位在第二个种族的所有单位和第三个种族的所有单位之前，第二个种族的所有单位在第三个种族的所有单位之前。但是注意：种族间的单位，他们的相对顺序不发生改变。

也就是说，如果给出先后顺序为Zerg,Terran,Protoss，那么所有为Zerg的单位排在最前面，紧接着是所有Terran的单位，最后是所有Protoss的单位。如果其中一个种族没有任何一个单位，则跳过该种族。

那么对于tokitsukaze拥有的n个单位，做完给定先后顺序的Race Sorting后，n个单位的顺序是什么？请按顺序输出每个单位的编号。

第一行包含一个正整数T(T≤20)，表示T组数据。
 
对于每一组数据：
第一行包含一个正整数n(1≤n≤1000)，表示有n个单位。
接下来n行，每行输入格式为：ID is race
其中，ID为一个正整数(1≤ID≤n)，数据保证ID唯一。race为一个字符串，保证是"Terran","Zerg","Protoss"三种中的一种(没有引号)。
最后一行包含一个字符串，格式为：race1,race2,race3。表示3种种族的先后顺序。
 
数据保证race1,race2,race3为"Terran","Zerg","Protoss"的一种排列(没有引号)。
 
详情请见样例。

对于每组数据：
按race1,race2,race3的顺序，在一行输出排序后的ID序列，两个ID用空格隔开，行末无多余空格。

死在了c++的sort上，这个sort是不稳定的，所以顺序换了，需要再按照原顺序排一下

实际上啥都没必要，只要对大写字母暴力跑一下就行了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4+7;
char A[10][100]={
    "Terran",
    "Zerg",
    "Protoss"
};
int Hash[10];
struct node{
    int id,op,x;
    bool operator < (const node &a) const{
        if(Hash[op]==Hash[a.op])
            return x<a.x;
        return Hash[op]<Hash[a.op];
    }
}Fu[maxn];
int sovle(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        Fu[i].x = i;
        scanf("%d",&Fu[i].id);
        scanf("%*s%s",A[3]);
        for(int j=0;j<3;j++)
            if(!strcmp(A[j],A[3]))
                Fu[i].op = j;
    }
    char s[100];
    scanf("%s",s);
    for(int i=0;s[i];i++){
        if(s[i]<='Z' && s[i]>='A'){
            for(int j=0;j<3;j++)
                if(A[j][0]==s[i])
                    Hash[j] = i;
        }
    }
    sort(Fu,Fu+n);
    for(int i=0;i<n-1;i++)printf("%d ",Fu[i].id);
    printf("%d\n",Fu[n-1].id);
    return 0;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--)
        sovle();
    return 0;
}

///直接跑
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3+7;
int A[maxn],n,ans[maxn],cnt;
char A_[maxn][20],op[20];
void sovle(){
    cnt = 0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>A[i]>>A_[i]>>A_[i];
    cin>>op;
    for(int i=0;op[i];i++){
        if(op[i]<='Z' && op[i]>='A'){
            for(int j=0;j<n;j++)
                if(A_[j][0]==op[i])
                    ans[cnt++] = A[j];
        }
    }
    for(int i=0;i<cnt-1;i++)printf("%d ",ans[i]);
    printf("%d\n",ans[cnt-1]);
}
int main(){
    int t;
    cin>>t;
    while(t--)
        sovle();
    return 0;
}

 

 

J.Carrier

在星际争霸2(StarCraftⅡ)中，航母(Carrier)是星灵(Protoss)最强的空中单位。

航母的建造，需要350水晶矿，250高能瓦斯，6人口。

现在tokitsukaze想要建造航母。

tokitsukaze拥有a水晶矿，b高能瓦斯。以及当前人口x，人口上限y。

当建造航母时，系统首先会判断玩家的水晶矿是否足够。若水晶矿不足，系统会提示:"You have not enough minerals."(矿物储量不足。)

若水晶矿足够，接着会判断玩家的高能瓦斯是否足够。若高能瓦斯不足，系统会提示:"You require more vespene gas."(高能瓦斯不足。)

若高能瓦斯也足够，会判断玩家的当前人口加上建造需要的人口是否超出人口上限。若超出人口上限，系统会提示:"You must construct additional pylons."(你需要建造更多的水晶塔。) 建造水晶塔(Pylon)能提高星灵的人口上限。

若没超出人口上限，tokitsukaze就能建造一艘航母了，那么系统会提示:"Carrier has arrived."(航母已经抵达。)

请问tokitsukaze在建造航母时，系统会发出什么提示。

第一行包含一个正整数T(T≤100)，表示T组数据。
对于每组数据：
第一行包含4个正整数a,b,x,y(1≤a,b≤1000,1≤x≤y≤200)。

对于每组数据：
输出一行，表示系统发出的提示。
注意：输出均不含引号。

签到题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char ans[4][100] = {
"You have not enough minerals.",
"You require more vespene gas.",
"You must construct additional pylons.",
"Carrier has arrived."
};
int main(){
    int t,a,b,x,y,flag;
    cin>>t;
    while(t--){
        flag = 3;
        cin>>a>>b>>x>>y;
        if(a<350)
            flag = 0;
        else if(b<250)
            flag = 1;
        else if(x+6>y)
            flag = 2;
        cout<<ans[flag]<<endl;
    }
 
    return 0;
}

 

K.Technology Tree

 

在星际争霸(StarCraft)中，有3个种族。对于任意一个种族，他们的建筑建造都是有一个顺序的。这个顺序正好是一个树形结构，我们称之为"科技树"(Technology tree)。

在科技树中，只有一个建筑是不需要前置建筑的，我们把这个建筑的编号设为1。其他的建筑，有且仅有一个前置建筑。

比如建筑2的前置建筑为建筑1，意思是只有先建造了建筑1，才能建造建筑2。

一个种族有n个建筑，建筑1没有前置建筑，建筑i(2≤i≤n)的前置建筑为f。每个建筑的建造都需要费用，建筑i(1≤i≤n)的建造花费为a晶体矿和b高能瓦斯。

现在tokitsukaze想知道，如果想要建造建筑x，总共需要消耗多少晶体矿和高能瓦斯。

第一行包含一个T(T≤10)，表示T组数据。
对于每组数据：
第一行包含两个正整数n，q(1≤n,q≤20000)，表示有n个建筑和q次查询。
接下来n行，每行包含两个整数a,b(0≤a,b≤300)，表示建造建筑i需要花费a晶体矿和b高能瓦斯。
接下来一行，包含n-1个正整数f(1≤f≤n)。第i个(1≤i＜n)正整数fi(1≤fi＜i)表示建筑i+1的前置建筑为fi。
接下来q行，每行包含一个正整数x，表示询问。

对于每个询问，输出一行，包含两个整数c,d(用空格隔开)，表示如果想要建造建筑x，总共需要消耗c晶体矿和d高能瓦斯。

跑一下dfs，把答案预处理在value数组里，然后每次输出即可，居然还可以直接加、

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e4+7;
ll ans[maxn][2],value[maxn][2];
int head[maxn],cnt;
struct node{
    int to,nex;
}Edg[maxn<<2];
void add(int u,int v){
    Edg[cnt] = {v,head[u]};
    head[u] = cnt++;
}
void init(){
    memset(head,-1,sizeof(head));
    cnt = 0;
}
void dfs(int cur,ll cry,ll Gaus){
    ans[cur][0] = cry,ans[cur][1] = Gaus;
    for(int i = head[cur];~i;i = Edg[i].nex)
        dfs(Edg[i].to,cry+value[Edg[i].to][0],Gaus+value[Edg[i].to][1]);
}
int main(){
    int t,n,q;
    cin>>t;
    while(t--){
        init();
        cin>>n>>q;
        for(int i=1;i<=n;i++)
            scanf("%d%d",&value[i][0],&value[i][1]);
        for(int i=1;i<=n-1;i++){
            int to;
            cin>>to;
            add(to,i+1);
        }
        dfs(1,value[1][0],value[1][1]);
        while(q--){
            int x;
            cin>>x;
            cout<<ans[x][0]<<" "<<ans[x][1]<<endl;
        }
    }
    return 0;
}

///每次直接加
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e4+7;
ll value[maxn][2];
int main(){
    int t,n,q;
    cin>>t;
    while(t--){
        cin>>n>>q;
        for(int i=1;i<=n;i++)
            scanf("%d%d",&value[i][0],&value[i][1]);
        for(int i=1;i<=n-1;i++){
            int to;
            cin>>to;
            value[i+1][0] += value[to][0];
            value[i+1][1] += value[to][1];
        }
        while(q--){
            int x;
            cin>>x;
            cout<<value[x][0]<<" "<<value[x][1]<<endl;
        }
    }
    return 0;
}

 

 

L.The Last Stand
 

tokitsukaze玩到了星际争霸2(StarCraftⅡ)自由之翼的最后一关战役:背水一战(The Last Stand)。

雷诺(Raynor)费劲千辛万苦终于找到了刀锋女王凯瑞甘(Kerrigan)，这时候雷诺收集齐了塞尔纳加上古神器。上古神器组装后可以净化被异虫感染的人类。

刀锋女王一开始位于坐标原点，她的初始生命为h，她要进攻位于m处的人类基地。

在进攻的过程中刀锋女王会选择触发一些事件来强化自身，但是因为受到塞尔纳加上古神器的影响，这些事件发生了反转，所以不一定都会给刀锋女王带来强化。

刀锋女王在进攻的过程中会路过n个事件的触发地，其中第i个事件的触发地点为pos[i]。当触发这个事件时，会立刻将刀锋女王的生命值变为H+val[i]，H为触发事件时刀锋女王的生命值，注意val[i]的值可能为正也可能为负。触发这个事件的同时，还会给刀锋女王添加一个buff。

为了简化问题，我们认为刀锋女王身上最多只能存在一个buff，也就是后来的buff会覆盖掉之前的buff效果，该buff会持续的改变刀锋女王的生命值，当刀锋女王身上存在buff时，她每往前走一个单位，她的生命值都会变为H+delta[i]，H为刀锋女王往前走一个单位前的生命值，注意delta[i]可能为正值，也可能为负值。我们认为一开始刀锋女王身上不具有任何的buff效果。

刀锋女王在路过某个事件的触发地时，她可以选择触发这个事件或者跳过不触发这个事件。不过聪明的刀锋女王总是会选择最优策略，这使她到达人族基地时拥有最多的生命值。

当刀锋女王的生命值小于等于0时，她就会死亡，在保证刀锋女王必须存活的条件下。她到达人族基地时的最大生命值是多少？（假设她的生命值上限无限大的前提下）

第一行输入一个正整数T(1≤T≤30)，表示有T组数据。
对于每组案例：
第一行输入三个正整数n,m,h(1≤n≤1000,1≤m≤10^9,1≤h≤10^9)分别表示有n个事件的触发地，刀锋女王要进攻位于m处的人族基地，刀锋女王的初始生命h。
接下来n行每行输入三个正整数pos[i],val[i],delta[i](1≤pos[i]<m ，-10^9≤val[i],delta[i]≤10^9)，分别表示第i个事件的触发地为pos[i]，如果刀锋女王触发该事件的话，会立刻改变她的生命val[i]点，并且会改变自身buff的状态，之后每往前走一步都会改变她的生命值delta[i]点。
输入保证这n个事件的触发地pos[i]是按照递增顺序输入的，并且pos[i]互不相同。

对于每组数据，请输出一行一个正整数表示刀锋女王在选择最优策略的情况下到达人族基地时自身生命的最大值。

猜一下，应该是dp，然后果然是，emm，怎么说呢，就是按照题意写一下，大概，还是看代码吧

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3+20;
ll t,n,m,h,dp[maxn],val[maxn],pos[maxn],delta[maxn];
void sovle(){
    memset(dp,0,sizeof(dp));
    cin>>n>>m>>h;
    for(int i=1;i<=n;i++)
        cin>>pos[i]>>val[i]>>delta[i];
    dp[0] = h;///初始生命值
    pos[n+1] = m;///终点
    for(int i=1;i<=n+1;i++){
        for(int j=0;j<i;j++){
            if(dp[j]+val[j]>0)///当不死亡时，到下一点的最大生命值
                dp[i] = max(dp[i],dp[j]+val[j]+(pos[i]-pos[j])*delta[j]);
        }
    }
    cout<<dp[n+1]<<endl;
}
int main(){
    cin>>t;
    while(t--)
        sovle();
    return 0;
}