作业

H1

A : 打酱油

问题描述

小明带着N元钱去买酱油。酱油10块钱一瓶，商家进行促销，每买3瓶送1瓶，或者每买5瓶送2瓶。请问小明最多可以得到多少瓶酱油。

输入格式

输入的第一行包含一个整数N，表示小明可用于买酱油的钱数。N是10的整数倍，N不超过300。

输出格式

输出一个整数，表示小明最多可以得到多少瓶酱油。

样例1

输入

40

输出

5

样例说明

把40元分成30元和10元，分别买3瓶和1瓶，其中3瓶送1瓶，共得到5瓶。

样例2

输入

80

输出

11

样例说明

把80元分成30元和50元，分别买3瓶和5瓶，其中3瓶送1瓶，5瓶送2瓶，共得到11瓶。

代码：

#include<iostream>
using namespace std;
​
int main(){
    int N=0,M=0;
    cin>>N;
    while(N>=50){
        N-=50;
        M+=7;
    }
    while(N>=30){
        N-=30;
        M+=4;
    }
    while(N>=10){
        N-=10;
        M+=1;
    }
    cout<<M<<endl;
    return 0;
}

B : 最小差值

问题描述

给定n个数，请找出其中相差（差的绝对值）最小的两个数，输出它们的差值的绝对值。

输入格式

输入第一行包含一个整数n。 第二行包含n个正整数，相邻整数之间使用一个空格分隔。

输出格式

输出一个整数，表示答案。

样例1

输入

5
1 5 4 8 20

输出

1

样例说明

相差最小的两个数是5和4，它们之间的差值是1。

样例2

输入

5
9 3 6 1 3

输出

0

样例说明

有两个相同的数3，它们之间的差值是0.

数据规模和约定

对于所有评测用例，2 ≤ n ≤ 1000，每个给定的整数都是不超过10000的正整数

代码：

#include<iostream>
using namespace std;

int main(){
    int n  =0, x = 0, result = 0;
    cin>>n;
    int *num = new int[n];
    for(int i = 0; i < n; i++)
        cin>>num[i];
    result =abs(num[0] - num[1]);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            x = num[i] - num[j];
            x = abs(x);
            result = min(x,result);
        }
    }
    cout<<result;
    return 0;
}

H2

A : 相邻数对

问题描述

给定 n 个不同的整数，问这些数中有多少对整数，它们的值正好相差 1。

输入格式

输入的第一行包含一个整数 n，表示给定整数的个数。 第二行包含所给定的n个整数。

输出格式

输出一个整数，表示值正好相差1的数对的个数。

样例输入

6
10 2 6 3 7 8

样例输出

3

样例说明

值正好相差1的数对包括 (2, 3), (6, 7), (7, 8)。

评测用例规模与约定

1≤n≤1000，给定的整数为不超过 10000的非负整数。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int cnt = 0;
    int *num = new int[n];
    for(int i = 0; i < n; i++){
        cin>>num[i];
    } //O(n)
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(num[i] - num[j] == 1 || num[j] - num[i] ==1){
                cnt++;
            }

        }
    } //O(n^2)
    cout<<cnt<<endl;
    return 0;
}

B : 门禁系统

问题描述

涛涛最近要负责图书馆的管理工作，需要记录下每天读者的到访情况。每位读者有一个编号，每条记录用读者的编号来表示。给出读者的来访记录，请问每一条记录中的读者是第几次出现。

输入格式

输入的第一行包含一个整数n，表示涛涛的记录条数。 第二行包含n个整数，依次表示涛涛的记录中每位读者的编号。

输出格式

输出一行，包含n个整数，由空格分隔，依次表示每条记录中的读者编号是第几次出现。

样例输入

5
1 2 1 1 3

样例输出

1 1 2 3 1

评测用例规模与约定

1≤n≤1000，读者的编号为不超过 n的正整数。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a;
    int num[1001] = {0};
    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>a;
        num[a]++;
        cout<<num[a]<<" ";
    } //O(n)
    return 0;
}

C : 桶装数字

问题描述

yhf有 n个桶，每个桶里都装着一些数字（一个或多个），所有的数字总共有 m个。这天，lzh把yhf所有的桶全打翻了，数字洒了一地！所幸，每个数字都有它所在的桶的标记。yhf希望恢复所有的桶，但是他还要刷考研题目，于是他拜托你来完成这个任务。 由于yhf能在一秒内完成一套考研数学题，因此他希望你的程序能在一秒内得出结果。

输入格式

第一行输入两个整数 n,m，第二行到第 m+1 行，每行两个整数 x,t，分别表示这个数字和它所在的桶。 保证每个桶至少含有一个数字。

输出格式

输出 n 行，若第 i个桶含有 ki个数字，则第 i行输出 ki个整数，表示这个桶内的数字。注意：输出每个桶的数字时应按升序排序输出。

样例输入

2 5
3 1
2 2
2 1
3 2
1 2

样例输出

2 3
1 2 3

评测用例规模与约定

对于60%的数据，1≤n,m≤1000 对于100%的数据，1≤n,m≤10^5,0≤x≤10^9,1≤t≤n

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m,n;//n个桶，m个数字
    int a,b;
    int cnt[100001] = {0};
    int num1[100001] = {0};//数字
    int num2[100001] = {0};//桶
    vector<int> v[100001];
    cin>>n>>m;
    for(int i = 0; i < m; i++){
        cin>>num1[i];
        cin>>num2[i];
        v[num2[i]].push_back(num1[i]); //O(1)
        cnt[num2[i]]++;
    }// O(n)
    for(int i = 1; i <= n; i++){
        sort(v[i].begin(),v[i].begin()+cnt[i]); //O(nlogn)
        for(vector<int>::iterator it = v[i].begin();it!=v[i].end();it++) 
            cout<<*it<<" ";  //O(n)
        cout<<endl;
    }  //O(n^2*logn)
    return 0;
}

D : 笔记本

问题描述

为了复习考研英语，yhf开始背单词。 yhf有一个笔记本，一开始是空的。当yhf遇到一个不认识的单词时，他会先查找笔记本，如果笔记本上没有，他就会先在互联网上查找这个单词，然后记在笔记本上。当yhf认为他已经熟记一个单词时，他会将这个单词在笔记本上擦掉（如果笔记本上没有就不用擦了）。yhf有时也会关心他的笔记本上记了多少单词，他会将笔记本上的单词按照字典序升序读一遍。 这天，yhf发现他的笔记本已经记满了单词，他决定用程序来实现笔记本的功能。但考虑到编写程序消耗的时间可以多背几千个单词，他决定把这个认为交给你。

输入格式

输入第一行包含一个整数 m，接下来有 m 行，每一行有一个整数 op，表示你的程序应执行哪种操作,具体如下

• op=1，后接一个单词，表示查找这个单词；如果笔记本中没有这个单词，则将单词写进笔记本

• op=2，后接一个单词，表示删除这个单词；如果笔记本中没有这个单词，则无需进行操作

• op=3，表示按字典序通读整个笔记本

输出格式

输出 m行，每一行表示输入的操作对应的输出，具体如下

• op=1，如果笔记本中有这个单词，输出found，否则输出write

• op=2，如果笔记本中有这个单词，输出erased，否则输出not found

• op=3，在一行内按字典序升序输出所有单词，中间用空格隔开

样例输入

8
1 problem
1 problem
2 problem
1 problem
2 acm
1 pro
1 acm
3

样例输出

write
found
erased
write
not found
write
write
acm pro problem

评测用例规模与约定

对于60%的数据，m≤100。 对于100%的数据，m≤10^5，单词长度∣s∣≤10 且由小写字母构成。 保证操作3的次数不超过3次。

代码：

#include<bits/stdc++.h>
using namespace std;
//set有序
int main(){
    int m, op, num = 0;
    string str;
    bool flag = 1;
    cin>>m;
    set<string> s;
    for(int i = 0; i < m; i++){
        cin>>op;
        switch (op){
            case 1:
                cin>>str; 
                if(s.count(str)){ //O(logn)
                    cout<<"found"<<endl;
                }   
                else{
                    s.insert(str);  //O(logn)
                    num++;
                    cout<<"write"<<endl;
                }
                break;
            case 2:
                cin>>str;
                if(s.find(str) != s.end()){   //O(logn)
                    cout<<"erased"<<endl;
                    s.erase(str);  //O(logn)
                    num--;
                }
                else
                    cout<<"not found"<<endl;
                break;
            case 3:{
                vector<string> v;
                for(set<string>::iterator it = s.begin(); it != s.end(); it++)
                    cout<<*it<<" ";      //set有序
                cout<<endl;
                break;
        }   
        default:
            break;
        }
    }
    return 0;
}

H3

A : 游戏

问题描述

有n个小朋友围成一圈玩游戏，小朋友从1至n编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，……，1号小朋友坐在n号小朋友的顺时针方向。 　　游戏开始，从1号小朋友开始顺时针报数，接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数（即数的个位）为k，则该小朋友被淘汰出局，不再参加以后的报数。当游戏中只剩下一个小朋友时，该小朋友获胜。 　　例如，当n=5, k=2时： 　　1号小朋友报数1； 　　2号小朋友报数2淘汰； 　　3号小朋友报数3； 　　4号小朋友报数4淘汰； 　　5号小朋友报数5； 　　1号小朋友报数6淘汰； 　　3号小朋友报数7； 　　5号小朋友报数8淘汰； 　　3号小朋友获胜。

给定n和k，请问最后获胜的小朋友编号为多少？

输入格式

输入一行，包括两个整数n和k，意义如题目所述。

输出格式

输出一行，包含一个整数，表示获胜的小朋友编号。

样例1

输入

5 2

输出

3

样例2

输入

7 3

输出

4

数据规模和约定

对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9。

笔记：

vector 的相关时间复杂度

pop_back(); //O(1)
erase(); //O(n)
push_back(); //O(1)
insert(); //O(n)
访问 O(1)

代码：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n = 0, k = 0;
    int nums = 0, j = 0;
    scanf("%d%d",&n,&k);
    vector<int> v;
    int i = 1;//用于计数
    if(k == 1){
        cout<<n<<endl;
        return 0;
    }
    for( ; i <= n; i ++){
        if(i%k == 0 || i%10 == k)
            continue;
        else{
            v.push_back(i); //插入N个元素， 则会引发lgN次的内存扩充,O(1)
            nums++;
        }
    } //O(n)
    while(nums > 1){
        if(i%k == 0 || i%10 == k){
            v.erase(v.begin()+j ); // erase删除的复杂度为O(n)
            nums--;
            j = j%nums;
        }
        else{
            j = (j + 1)%nums;
        }
        i++;
    } //O(N^2)
    printf("%d\n",v[0]);
    return 0;
}

B : 跳一跳

问题描述

近来，跳一跳这款小游戏风靡全国，受到不少玩家的喜爱。 　　简化后的跳一跳规则如下：玩家每次从当前方块跳到下一个方块，如果没有跳到下一个方块上则游戏结束。 　　如果跳到了方块上，但没有跳到方块的中心则获得1分；跳到方块中心时，若上一次的得分为1分或这是本局游戏的第一次跳跃则此次得分为2分，否则此次得分比上一次得分多两分（即连续跳到方块中心时，总得分将+2，+4，+6，+8…）。 　　现在给出一个人跳一跳的全过程，请你求出他本局游戏的得分（按照题目描述的规则）。

输入格式

输入包含多个数字，用空格分隔，每个数字都是1，2，0之一，1表示此次跳跃跳到了方块上但是没有跳到中心，2表示此次跳跃跳到了方块上并且跳到了方块中心，0表示此次跳跃没有跳到方块上（此时游戏结束）。

输出格式

输出一个整数，为本局游戏的得分（在本题的规则下）。

样例输入

1 1 2 2 2 1 1 2 2 0

样例输出

22

数据规模和约定

对于所有评测用例，输入的数字不超过30个，保证0正好出现一次且为最后一个数字。

代码：

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int score = 0;
    int temp = 1;
    int nums;
    while(scanf("%d",&nums) && nums != 0){
        if(nums == 1){
            temp = 1;
            score += temp;
        }
        else{
            if(temp == 1){
                temp = 2;
                score += temp;
            }
            else{
                temp += 2;
                score += temp;
            }
        }
    } //O(N)
    printf("%d\n",score);
    return 0;
}

C : 奇怪的电梯

问题描述

小H有一个奇怪的电梯，电梯可以根据需要停在每个楼层，每个楼层上都对应一个数字K_i（0 <= K_i <= N），该电梯只有两个按钮：“UP"和"DOWN”。在第i层楼，如果按下"UP"按钮，电梯将移动到i+K_i层；如果按下"DOWN"，电梯将移动到i-K_i层。当然，电梯有一个移动的范围，不能高于N且不能低于1。例如，有一个5层楼的建筑物，k_1 = 3，k_2 = 3，k_3 = 1，k_4 = 2，k_5 =5。从一楼开始，按"UP"按钮，将上升到四楼，如果按"DOWN"按钮，电梯将无法移动，因为它不能下降到-2楼。 现在问题来了：小H想从A层移动到B层，他至少要按几次"UP"或"DOWN"按钮，你能帮帮他嘛？

输入格式

输入包含多个测试用例。每个测试用例包含两行。 第一行包含上述三个整数N，A，B（1 <= N，A，B <= 200），第二行包含N个整数k_1，k_2，.... k_n​。 若读取到单个0，则表示输入结束。

输出格式

对于每个测试用例，输出一个整数表示最少按下"UP"或"DOWN"按钮的次数，若无法到达B层，请输出"-1"。每个测试用例的输出占一行。

样例输入

5 1 5
3 3 1 2 5
0

样例输出

3

数据规模和约定

1<=N,A,B<=200,0<=k_i<=N

提示

隐式图问题

代码：

#include<bits/stdc++.h>
using namespace std;
map<int, int> father;
queue<int> q;
void check(int x, int y){
    if(father.find(y) == father.end()){//y没有到达过  O(logn)
        q.push(y);   //O(logn)
        father[y] = x; //y的上一个状态是x
    }
}//O(logn)
void bfs(int A, int B, int N, int *k){
    int now = A;
    q.push(now); //O(1)
 
    while(!q.empty()){
        now = q.front();  //O(1)
        q.pop();  //O(1)
        if(now == B){
            int u = now;
            stack<int> temp;
            while(u != A){
                temp.push(u);
                u = father[u];
            }
        //    temp.push(u);
             printf("%d\n",temp.size());
            return;
        }
        if(now + k[now] <= N)
            check(now, now + k[now]);
        if(now - k[now] >= 1)
            check(now, now - k[now]);
    }
    printf("-1\n");
}
int main(){
    int N,A,B;
    while(scanf("%d",&N) && N!=0){
        scanf("%d",&A);
        scanf("%d",&B);
        int *k = new int[N+1];
        for(int i = 1; i <= N; i++){
            scanf("%d",&k[i]);  //O(N)
        }
        while(!q.empty()) q.pop();  //清空队列O(n)
        father.clear();
        bfs(A,B,N,k);
        delete k;
    }  //O(N^2)
    return 0;
}

D : 选数

问题描述

已知n个整数 x_1,x_2,…,x_n 和1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3,x_1=3,x_2=7,x_3=12,x_4=19时，可得全部的组合与它们的和为：

3+7+12=223+7+12=22 3+7+19=293+7+19=29 7+12+19=387+12+19=38 3+12+19=343+12+19=34

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=293+7+19=29。

输入格式

输入包含两行 第一行两个数n,k 第二行n个数依次表示x_i

输出格式

一个整数，表示合法的组合数

样例输入

4 3
3 7 12 19

样例输出

1

数据规模和约定

1<=k<n<=20 1<=x_i<=5000000

提示

素数的判定方法

bool prime(int n)
{
        if（n==1) return false;
        if (n==2) return true;
	for(int i=2;i*i<=n;i++)
	   if (n%i==0) return false;
	return true; 
}

代码：

#include<bits/stdc++.h>
using namespace std;
 
bool prime(int n){
    if (n==1) return false;
    if (n==2) return true;
	for(int i=2;i*i<=n;i++)
	   if (n%i==0) return false;
	return true; 
}
 
int main(){
    int n,k,cnt = 0;
    scanf("%d%d",&n,&k);
    int *a = new int[n];
    for(int i = 0; i < n; i++)
        scanf("%d",&a[i]); //O(n)
    int *b = new int[n];
    for(int i = 0, sum = pow(2,n); i< sum; i++){
        int nums = 0;
        int result = 0;
        int temp = i;
        result = 0;
        for(int j = 0; j < n; j++){
            b[j] = temp%2;//二进制表示每个输入的数取或不取
            temp /=2;
        } //O(N)
        for(int j = 0; j < n; j++)
            nums += b[j];
        if(nums == k){
            for( int j = 0; j < n; j++)
                result += b[j]*a[j];
            if (prime(result)) cnt ++; //O(logn)
        }
    }//O(2^n*n)
    printf("%d\n",cnt);
    return 0;
 
}

E : 棋盘问题

问题描述

小H收集到一些形状特殊的棋盘，她想在棋盘上面摆放棋子（棋子都是相同的）。她希望摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，你能帮她求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案数C嘛？

输入格式

输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。 注意只有#棋盘区域可以摆放棋子。

输出格式

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）

样例输入

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

样例输出

2
1

数据规模和约定

1<=k<=n<=8

代码：

#include<bits/stdc++.h>
using namespace std;
 
int nums = 0;
int vis[9] = {0}; //记录数字是否被使用
bool a[9][9];
char c;
void permutation(int x, int y, int n, int k){
    if( y == k){
        nums++;
        return;
    }
    for(int i = x; i < n; i++)
        for(int j = 0; j < n; j++){
            if(vis[j] == 0 && a[i][j]) { //此列未被放置且此位置可以放置
                vis[j] = 1;
                permutation(i+1,y+1,n,k);
                vis[j] = 0;
            }
        }
}
 
int main(){
    int n,k;
    while(scanf("%d%d",&n,&k) && n != -1 && k != -1){
        int i = 0;
        for (int j = 0; j < n; j++){
            for (int i = 0; i < n; i++){
                cin >> c;
                if (c == '#')//棋盘区域，可以摆放棋子
                    a[i][j] = 1;
                else
                    a[i][j] = 0;
            }
        }//O(n^2)
        for(int i = 0; i <= n; i++){ //每一组数据
        	nums = 0;
        	permutation(0,0,n,k);
    	}
    	cout<<nums<<endl;
    }
    return 0;
}

H4

A : 摆放垃圾桶

题目描述

滨海公园旁边新铺了一条路，把这条路分成n段，依次编号为1…n。为了防止游客把垃圾扔到海里，war要在路上放一些垃圾桶🚮。政府提出了m个要求，每个要求包含三个整数l，r，k，表示路段l到r之间至少有k个垃圾桶 。垃圾桶放太多不仅浪费资源，也影响风景，所以每个路段至多可以放一个垃圾桶。为了环保♻️，war最少要放多少个垃圾桶才能满足要求？

输入描述

第一行为n(1≤n≤3*10^4)，表示路段数。

第二行为m(1≤m≤5000)，表示要求数。

下面m行，每行描述一条建议l，r，k，用一个空格分隔，(1≤l≤r≤3*10^4,k≤r-l+1)。

输出描述

输出只有一个数，为满足政府所有的要求，需要的垃圾桶的最少数量。

Case 1

Input

9
4 
1 4 2 
4 6 1 
8 9 2 
3 5 2 

Output

4

代码：

#include<bits/stdc++.h>
//#include<iostream>
using namespace std;
//按照区间右端点大小升序排列，依次遍历各个区间，
//从左到右看该区间已有的垃圾桶数量，再从左到右，若数量不够则增加。

int n;  //表示路段数
int m;  //表示要求数
struct demand{
    int l,r,k; //表示路段l到r之间至少有k个垃圾桶
};

struct demand d[5000];

int cnt = 0; //记录垃圾桶个数

bool cmp(demand a,demand b){
    return a.r<=b.r;
}

int main(){
    scanf("%d",&n);
    scanf("%d",&m);
    bool *vis = new bool[n];  //记录该路段是否放置垃圾桶
    for(int i = 0; i < n; i++)
        vis[i] = 0;
    for(int i = 0; i < m; i++){
        scanf("%d",&d[i].l);
        scanf("%d",&d[i].r);
        scanf("%d",&d[i].k);
    }
    sort(d,d+m,cmp);
    for(int i = 0; i < m; i++){
        int temp = 0; //记录这一段要求里已经有的垃圾桶数量
        for(int j = d[i].l; j <= d[i].r; j++)  //从左到右看该区间已有垃圾桶数量
            if(vis[j]) temp++;
        for(int j = d[i].r; j >= d[i].l; j--){  //从右到左，若数量不够则增加
            if(!vis[j] && temp <= d[i].k){
                vis[j] = 1;
                temp ++;
                cnt ++;
            }
        }
    } //O(n^2)
    printf("%d\n",cnt);
    return 0;
}

B : 看电影

题目描述

终于可以随意出入校园啦！于是，n个人决定去看电影🎬。每个人都要先去A影院再去B影院。第i个人在A，BA，B影院的观影时间分别为a_i,b_ia**i,b**i。按照疫情防控要求，每个影院最多允许1人同时观影。那么怎样安排这n个人的观影顺序，能使所有人都在A,BA,B影院观影完的总时间最少。

输入描述

第一行为n(0<n<1000)(0<n<1000)，表示人数。

第二行n个数，第i个数为a_i(1≤a_i≤350)，中间有空格。

第三行n个数，第i个数为b_i(1≤b_i≤350)，中间有空格。

输出描述

输出只有一个数，为最少的总时间。

提示

贪心，可能需要了解Johnson法则

Input

5
3 5 8 7 10
6 3 2 5 8

Output

35

代码：

#include<bits/stdc++.h>
using namespace std;
//流水作业调度问题的Johnson算法
// (1)令N1 = { i | ai < bi}, N2 = { i | ai >= bi };
// (2)将N1中作业依ai的非减序排序；将N2中作业依bi的非增序排序；
// (3)N1中作业接N2中作业构成满足Johnson法则的最优调度。
struct time_{
    int a;
    int b;
};

bool cmp1(time_ A, time_ B){
    return A.a < B.a;
}
bool cmp2(time_ A, time_ B){
    return A.b > B.b;
}
//令N1 = { tt[i] | ai < bi}, N2 = { tt[i] | ai >= bi }
int main(){
    int n; //观影人数

    int numN1 = 0;
    int numN2 = 0;

    vector<time_> N1;
    vector<time_> N2;
    
    scanf("%d",&n);
    time_ tt[1005];
    for(int i = 0; i < n; i++)
        scanf("%d",&tt[i].a);
    for(int i = 0; i < n; i++)
        scanf("%d",&tt[i].b);
    for(int i = 0; i < n; i++){
        if(tt[i].a < tt[i].b){
            N1.push_back(tt[i]);
            numN1++;
        }
        else{
            N2.push_back(tt[i]);
            numN2++;
        }
    }
    //将N1中依ai的增序排序；将N2中依bi的非增序排序；
    sort(N1.begin(),N1.begin()+numN1,cmp1);  //O(nlogn)
    sort(N2.begin(),N2.begin()+numN2,cmp2);  //O(nlogn)
    int timeA = 0;
    int timeB = 0;
    timeB = (numN1 > 0) ? N1[0].a : N2[0].a;
    for(int i = 0; i < numN1; i++){ 
        timeA += N1[i].a;       //N1中A的时间
        timeB += N1[i].b;       //N1中B的时间
    }
    for(int i = 0; i < numN2; i++){  //N2中ai>=bi，可能出现B等待
        timeA += N2[i].a;
        timeB = (timeB <= timeA) ? timeA + N2[i].b : timeB + N2[i].b;
    }  //timeB取较大的
    printf("%d\n",timeB);
    return 0;
}

C : 划分石头

题目描述

海边有很多好看的石头🪨，war把它们收集起来依次排成一排，一共n个，第i个石头的重量为w_i。他想将其分成m段，每一段连续，并且重量和最大的段的和最小。请你帮帮他～

输入描述

第一行为n(1≤n≤10^5)，m(m≤n)。

第二行n个数，第i个数为w_i(0≤wi≤10^9)，中间有空格。

输出描述

输出只有一个数，重量和最大的段的和。

提示

二分答案

Input

6 3
4 2 4 5 1 1

Output

7

代码：

#include<bits/stdc++.h>
using namespace std;

//end()函数返回一个指向当前vector末尾元素的下一位置的迭代器.要访问末尾元素,需要先将此迭代器减1。

/*最大值最小化问题
n个正整数的序列划分成m个连续的子序列，各个序列的和为sum，使得最大的sum尽可能地小
在每次划分中找一个上限mid，使得每组序列和小于mid，超出了就放到下一个序列
利用二分查找，在max和总和中不断找，直到l>r
*/
int n; //石头个数n
int m = 0; //分成m段

int main(){
    int sumw = 0;   //总重量
    int maxw = 0;
    scanf("%d%d",&n,&m);
    int *w = new int[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&w[i]);    
    } //O(n)
    for(int i = 0; i < n; i++){//求重量总和以及最大重量
        if(maxw < w[i]) maxw = w[i];  
        sumw+=w[i];
    }  //O(n)
    vector<int> a;
    int mid;
    int l = maxw, r = sumw;
    int cnt = 0;
    while(1){
        cnt = 0;
        mid = (l+r)/2;
        a.push_back(w[0]); //O(1)
        cnt ++;
        for(int i = 1; i < n; i++){
            if(*(--a.end())+w[i] > mid){
                a.push_back(w[i]);  //O(1)
                cnt++;
            }
            else{
                int temp = *(--a.end());  //O(1)
                temp += w[i];
                a.erase(--a.end());  //O(1)
                a.push_back(temp);    //O(1)
            }        
        }
        if(cnt > m)  //继续增加每一段总和的大小   
            l = mid + 1;
        else     
            r = mid;
        if(l < r)
            a.clear();
        else 
            break;
    } 
    //O(nlog(sumw-maxw))
    int maxnum = 0;
    for(vector<int>::iterator it = a.begin(); it != a.end(); it++)
        if(*it > maxnum)
            maxnum = *it;   //O(n)
    printf("%d\n",maxnum);
    return 0;
}

D : 捡贝壳

题目描述

war发现海边还有好看的贝壳，他把n个贝壳依次排成一排，第i个贝壳的体积为v_i。war觉得平均体积最大，且长度不小于m的一段贝壳最好看。请你帮他找出这一段～

输入描述

第一行为n(1≤n≤10^5)，m(m≤n)。

第二行n个数，第i个数为v_i(0≤vi≤2000)，中间有空格。

输出描述

输出一个整数，表示这个平均体积的1000倍。不用四舍五入，直接输出。

提示

二分答案，可能需要用到前缀和思想

Input

12 6
1
1
1
1
1
1
1
1
1
1
1
1

Output

1000

代码：

#include<bits/stdc++.h>
using namespace std;

/*二分求平均值，l和r不断找
对于一个中间值，将v数组中的每个数减去mid，只要存在一个长度大于k的子序列和大于0
说明此平均数可行

判断
将v数组中的每个值减去mid（在累加的时候减就好）
求出前m个数的和currentsum
currentsum：当前位置的前缀和
leftsum：在循环中求出当前指向位置的左侧m个位置的前缀和
minleftsum：左侧最小的前缀和(rightsum-minleftsum)就是最大和序列
若最大和序列大于0，说明此平均值可行
*/

int n,m; //n个贝壳，长度大于等于m
int result;  //输出

int main(){
    scanf("%d%d",&n,&m);
    int *v = new int[n];
    scanf("%d",&v[0]);
    double l=v[0],r=v[0];  
    for(int i = 1; i < n; i++){
        scanf("%d",&v[i]);
        if(l > v[i]) //求最小
            l = v[i];
        if(r < v[i]) //求最大
            r = v[i];
    } //O(n)
    double mid;
    while(l + 1e-5 < r){
        bool flag = 0;
        mid = (l + r)/2.0;
        double currentsum = 0.0,leftsum = 0.0, minleftsum = 0.0;
        for(int i = 0; i < m; i++)
            currentsum += v[i] - mid;  //O(m)
        for(int i = m; i <= n; i++){
            if(currentsum - minleftsum > 0){
                flag = 1;
                break;
            }
            if(i!=n){
                currentsum += v[i]-mid;
                leftsum += v[i-m]-mid;
                minleftsum = min(minleftsum,leftsum);
            }
        }  //O(n)
        if(flag)
            l = mid;
        else 
            r = mid;
    } //O(nlogn)
    result = r*1000;
    printf("%d\n",result);
    return 0;
}

H5

A : 巨石迷阵

问题描述

听说这片土地埋藏着什么秘密，来到这片土地的人不计其数，有人说这里财宝无数，也有人说这里是上古文明留下来的遗迹。小 L 收集情报和资料很久了，只身一人历经千辛万苦终于来到了这片地域的中心地带。突然，四周升起许多巨石，不出所料，面前的正是巨石迷阵。

你面前有 nn 块巨石排成一行，每个上面有一个大写字母。 接下来有 mm 个询问，每一个询问包含两个数字 l,rl,r ，对于每个询问，你需要回答这个处于区间 l,r 的石块上的字母是否每一个英文字母都至少出现了一次。

输入格式

第一行一个整数 nn , n\le5\times10^5n≤5×105 第二行，一个长度为 nn 的字符串 第三行，一个整数 mm, m\le5\times10^5m≤5×105 接下来的 mm 行，每行两个整数表示 l,r,1\le l\le r\le nl,r,1≤l≤r≤n

输出格式

输出包含 mm 行，每行一个 \text{YES}YES ,或者 \text{NO}NO 。 分别表示是否每个字母都至少出现一次。

样例输入

30
AAABCDEFGHIJKLMNOPQRSTUVWXYZAA
5
1 26
2 27
3 28
4 29
5 30

样例输出

NO
NO
YES
YES
NO

代码：

#include<bits/stdc++.h>
using namespace std;
 
int n;  //n块巨石
int m;  //m个询问
int l,r;  //每个询问包含两个数字，对于每个询问，回答处于区间[l,r]是否每个字母至少出现一次

int s[500010][26] = {0};


int main(){
    scanf("%d",&n);
    char c;   //字符
    for (int i = 1; i <= n; i++){
        cin>>c;
        s[i][c-'A'] = 1;
    }
    scanf("%d",&m);
    for (int i = 0; i < 26; i++){
        for(int j = 2; j <= n; j++){
            s[j][i] += s[j-1][i];
        }
    }  //求前缀和 O(26n)
    for(int i = 0; i < m; i++){
        bool yn = 0;
        scanf("%d%d",&l,&r);
        for(int j = 0; j < 26; j++){
            if (s[r][j] - s[l-1][j] >= 1){
                continue;
            }
            else{
                yn = 1;
                printf("NO\n");
                break;
            }
        }
        if(yn == 0)
            printf("YES\n");
    }
    return 0;
}

B : 有惊无险

问题描述

解决了巨石迷阵，小 L 长舒一口气。他坐在一棵繁茂的树下刚打开地图，突然，四周轰隆隆又一阵巨响，面前又出现了许多巨石。

情报有误！情报有误！！

根据搜集来的情报，这里不应该再次出现这么多巨石！ 小 L 赶忙起身，屏气凝神，重新专注起来…

有一个长度为 nn 的字符串，找到一个区间 l,r，使得处于区间 l,r 的石块上的字母，26个大写字母都至少出现一次。输出这个区间长度的最小值。

数据保证有解

输入格式

第一行一个整数 nn , n\le2\times10^5n≤2×105 第二行，一个长度为 nn 的字符串

输出格式

一行，一个数，代表最短长度

样例输入

30
AABBCDEFGHIJKLMNOPQRSTUVWXYZZZ

样例输出

27

代码：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;  //n块巨石
    int l,r;  //找到一个区间 [l,r],使得处于区间[l,r]的石块上的字母,26个大写字母都至少出现一次.
    int s[200010][26] = {0};
    scanf("%d",&n);
    char c;   //字符
    for (int i = 1; i <= n; i++){
        cin>>c;
        s[i][c-'A'] = 1;
    }
    for (int i = 0; i < 26; i++){ 
        for(int j = 2; j <= n; j++){
            s[j][i] += s[j-1][i];
        }
    }   //求前缀和 O(26n)
    l = 1;
    r = 1;
    int length = n;
    bool flag = 0;
    while(1){
        for(int i = 0; i < 26; i++){
            if(s[r][i] - s[l-1][i] >= 1){
                if(i == 25){
                    length = min(r - l + 1, length);
                    l++;
                }  //依次遍历26个字母，如果i==25，说明该区间满足条件，更新length 长度
            //    continue;
            }
            else{
                if(r == n){
                    flag = 1;
                    break;
                }  
                r++;
                break;  //若遇到某一个字母前缀和为0，说明该区间不满足，break，遍历下一区间。
            } 
        }
        if(flag)
            break;
    }
    printf("%d\n",length);
    return 0;
}

C : 天降甘霖

问题描述

不知道又走了几天，眼前是一片整齐的青石地砖。不管是谁看上一眼，就知道这绝对不是自然生成的。当小 L 踏上青石地板的一瞬间，原本晴朗的天空迅速暗了下来。紧接着乌云密布，下起了雨。雨很快就停了，紧接着天空瞬间放晴，开始升温。潮湿的青石板被很快晒干。

“这是夏天了吗，雨来得快去得也快啊。”长时间孤身一人，小 L 经常自言自语。

但敏锐的 小 L 发现，有一些青石板上的痕迹没有被完全晒干，雨痕竟然拼成了数字。

有一行 n个数。输出每k个相邻数字的最大值和最小值。

输入格式

第一行两个整数 n,k,1≤k≤n≤10^6 第二行，有 n个数字，中间用空格隔开，每一个数为大小不超过 10^9的正整数。

输出格式

有两行，每行 n-k+1个数字，第一行表示最小值，第二行表示最大值。

样例输入

8 3
1 3 -1 -3 5 3 6 7

样例输出

-1 -3 -3 -3 3 3
3 3 5 5 6 7

代码：

#include<bits/stdc++.h>
using namespace std;
 
//有一行n个数。输出每k个相邻数字的最大值和最小值。
 
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    int *num = new int[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&num[i]);
    }
    int length = 0;
    deque<int> q1,q2;
    q1.push_back(0);
    q2.push_back(0);
    for(int i = 1;i < n; i ++){
        if (!q1.empty() && i-q1.front() == k )
            q1.pop_front();
        while (!q1.empty()){
            //满足单调递减队列
            if(num[q1.back()] >= num[i])
                q1.pop_back();
            else 
                break;
        } 
        q1.push_back(i);
        if (i >= k-1)
            printf("%d ",num[q1.front()]);
    }
    printf("\n");
    for(int i = 1; i < n; i++){
        if (!q1.empty() && i-q2.front() >= k )
            q2.pop_front();
        while (!q2.empty()){
        //满足单调递增队列 
            if (num[q2.back()] <= num[i])
                q2.pop_back();
            else
                break;
        } 
        q2.push_back(i);
        if (i >= k-1)
            printf("%d ",num[q2.front()]);   
    }
 //    system("pause");
    return 0;
}

D : 终而复始

问题描述

青石板路的尽头堆满了财宝。小 L 感到很一阵阵失望，只能先搬走一部分财宝了。

财宝是一个个矩形紧紧挨在一起，第i个矩形宽度为1，高度是h_i

小L是一个不会贪心不贪心的人，所以决定只拿走最大矩形的面积这么多。

拿着拿着，小L突然想到，其实这个财宝墙后面还是有路的。

输入格式

第一行一个整数 n, n≤10^5 第二行，一行数，第i个数代表 h_i, 1≤h_i≤10^9

输出格式

一行，一个数，代表最大矩形面积

样例输入

7
2 1 4 5 1 3 3 

样例输出

8

代码：

#include<bits/stdc++.h>
using namespace std;

//对每一个矩形向左右延展，若高度大于当前宽度，则加一，求出最大宽度

//创建一个空栈
// 从第一个矩形条开始，对每个矩形条的高度height[i] ，i的取值范围是[0,n-1])执行下面两步
// a) 如果栈为空，或height[i]大于等于栈顶元素，那么将矩形条i压入栈中。
// b)如果输入的矩形条高度小于栈顶元素高度，那么将栈顶元素在输入数组中的索引tp出栈，然后计算矩形面积。矩形的高为height[tp]，而右边界为i，左边界为当前栈顶元素对应的索引，若栈为空，则宽度就是i。
// 经过计算后，栈非空，然后将栈中元素逐个弹出，并按照步骤2计算矩形面积，并且更新最大值。
int main(){
    int n;  //个数
    scanf("%d", &n); 
    int *height = new int[n]; //矩形的高
    int *width = new int[n];  //矩形的宽
    for(int i = 0; i < n; i++)
        width[i] = 1;
    long long maxsize = 0;
    for(int i = 0; i < n; i++)
        scanf("%d",&height[i]);
    stack<int> st;
    int temp;
    for(int i = 0; i < n; ){
        if(st.empty() || height[st.top()] <= height[i])
            st.push(i++); //高度比栈顶元素的高度大 入栈
        else{
            temp = st.top();
            st.pop();
            if(st.empty())
                maxsize = max(maxsize,(long long)height[temp] * i);
            else
                maxsize = max(maxsize,(long long)height[temp] * (i - st.top()-1));
        }
    }
    while(!st.empty()){
        temp = st.top();
        st.pop();
        if(st.empty())
            maxsize = max(maxsize,(long long)height[temp] * n);
        else
            maxsize = max(maxsize,(long long)height[temp] * (n - st.top()-1));
    }

    // for(int i = 0; i < n; i++){
    //     for(int j = i+1; j < n; j++){
    //         if(height[j] >= height[i])
    //             width[i] ++;
    //         else 
    //             break;
    //     }
    //     for(int j = i-1; j >= 0; j--){
    //         if(height[j] >= height[i])
    //             width[i] ++;
    //         else
    //             break;
    //     }
    // }
    // for(int i = 0; i < n; i++)
    //     maxsize = max((long long)height[i] * width[i], maxsize);
    cout<<maxsize;
//    printf("%d",maxsize);
    return 0;
}

E : 旅途不止

问题描述

小 L 至今没有回来。这太正常，就像其他没有回来的探险者一样。没有人会提起小 L ，也没有人述说小 L 的故事。 多年以后，你也踏上了这片神秘的土地，眼前出现了一道谜题。

有一列长度为n的数，初始值都是1。 有m次操作，每次对属于区间 [l,r]的数都乘上一个数 c^b，最后输出这n个数的最大公约数。

谜题面前有一张地图，上面署名 “小 L”。

输入格式

第一行一个整数n, n≤10^5 第二行，一个整数 m, m≤10^5 接下来的m行，每行四个整数表示 l,r,c,b 1≤l≤r≤n,1≤c≤100,0≤b≤10^9

输出格式

一行，一个数，代表最大公约数，答案对10^9+7取模。

样例输入

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

样例输出

3

初始：[1,1,1,1,1] 第一次操作后，[9,9,9,9,1] 第二次操作后，[9,36,36,36,1] 第三次操作后，[9,36,216,216,6]

gcd(9,36,216,216,6)=3，gcd表示最大公约数

地图上画的正是当年小 L 探索过的区域，但小 L 去了哪里还是不得而知。 地图的背面，写着如下内容：

n个数的最大公约数求法：

设第i个数为 a_i，则 a_i=∏jp_j^b_ij，其中p_j表示第j个素数，b_ij表示第i个数质因数分解之后 p_j的幂次。 则 gcd(a_1,...,a_n)=∏j​p_j^minbij​​。

举例求 gcd(60,24,36,42)

60=2^2×3^1×5^1×7^0 24=2^3×3^1×5^0×7^0 36=2^2×3^2×5^0×7^0 42=2^1×3^1×5^0×7^1

所以

gcd(60,24,36,42)=2^min(2,3,2,1)×3^min(1,1,2,1)×5^min(1,0,0,0)×3^min(0,0,0,0)=2^1×3^1×5^0×7^0=6

代码：

#include<bits/stdc++.h>
using namespace std;
//有一列长度为n的数,初始值都是1
//有m次操作,每次对属于区间[l,r]的数都乘上一个数c^b,最后输出这n个数的最大公约数

//快速幂
long long qpow(long long a,long long b,long long m){
    long long ans=1;
    if(!b) 
        return 1;
    while(b>0){
        if(b&1) 
            ans=ans*a%m;
        a=a*a%m;
        b=b>>1;
    }
    return ans;
}

int n,m,l,r,c;
long long b;
int prime_number[25] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int main(){
    scanf("%d",&n);
    scanf("%d",&m);
    long long num[n+2][25] = {0};   //n行25列的矩阵
    for(int i = 0; i < m; i++){
        scanf("%d%d",&l,&r);
        scanf("%d",&c);
        cin>>b;
        for(int i = 0; i < 25; i++){
            if(c < prime_number[i])
                break;
            else{
                while(c % prime_number[i] == 0){
                    num[l][i] += b;  //本应该在[l,r]区间每一个数加b
                    num[r+1][i] -= b;
                    c/=prime_number[i];   
                }
            }
        }
    }
    long long minnum[25] = {0};
    for(int i = 0; i < 25; i++){
        minnum[i] = num[1][i];
    }
    for(int i = 0; i < 25; i++){
        for(int j = 2; j <= n; j++){
            num[j][i] = num[j][i] + num[j-1][i];
            minnum[i] = min(num[j][i],minnum[i]);
        }
    }  //求每一个质数对应的最小值，即求最大公约数
    // for(int i = 0; i <= n; i++){
    //         for(int j = 0; j < 25; j++){
    //             cout<<num[i][j]<<" ";  
    //         }
    //         cout<<endl;
    // }
    long long m = 1e9+7;
    long long ans = 1;
    for(int i = 0; i < 25; i++){
        ans = ans * qpow(prime_number[i],minnum[i],m) % m;
    }
    cout<<ans<<endl;
    return 0;
}

H6

A : 元音跳跃

问题描述

现在有一个长度为n的字符串，都有小写字母组成。 输出最长的连续元音的长度

输入格式

第一行一个整数n,0≤n≤10^6 接下来一行表示字符串

输出格式

输出一行，一个数，代表答案

样例输入

10
aeioubaeio

样例输出

5

代码：

#include<bits/stdc++.h>
using namespace std;

//现在有一个长度为n的字符串，都有小写字母组成。
//输出最长的连续元音的长度
int main(){
    int n;
    char c;
    bool flag = 1;
    int ans = 0;
    int length = 0;
    scanf("%d",&n);
    for(int i = 0; i < n; i ++){
        cin>>c;
        if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
            if(flag)
                length ++;
            ans = max(length,ans); 
            flag = 1;
        }
        else{
            length = 0;
        }
    }
    printf("%d\n",ans);
    return 0;
}

B : 元音删除

问题描述

现在有一个长度为n的字符串，都有小写字母组成。 现在要将所有相连的元音只保留第一个，并将其他元音删除

输出删除完之后的字符串

输入格式

第一行一个整数 n, 0≤n≤10^6 接下来一行表示字符串

输出格式

输出一行，一个字符出

样例输入

11
aeioubaeiou

样例输出

aba

代码：

#include<bits/stdc++.h>
using namespace std;

//现在有一个长度为n的字符串，都有小写字母组成。
//现在要将所有相连的元音只保留第一个，并将其他元音删除

int main(){
    int n;
    bool flag = 0; //标记之前的字母是否为元音
    vector<char> v;
    char c;
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        cin>>c;
        if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
            if(flag)
                flag = 1;
            else{
                v.push_back(c);
                flag = 1;
            }
            
        }
        else{
            flag = 0;
            v.push_back(c);
        }
    }
    for(vector<char>::iterator it = v.begin(); it != v.end(); it++){
        cout<<*it;
    }
    return 0;
}

C : 公路修建

问题描述

你现在是城市的主人 现在有n个村庄，要修建m条路，每修建一条路，道路是双向的，输出至少还需要修建几条，可以让所有村庄互相可达。 一开始路为0条

数据保证有解

输入格式

第一行两个整数 n,m, 0≤n,m≤10^5 接下来有m行，每行 a,b代表修建了一条从第a个村庄，到第b个村庄的路。 1≤a,b≤n a和b可能相同。

输出格式

一共m行，第i个数代表已经修建了前i条路时，最少还需要修建几条，可以让所有村庄互相可达。

样例输入

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

样例输出

4
3
2
2
2

代码：

#include<bits/stdc++.h>
using namespace std;

//现在有n个村庄，要修建m条路，每修建一条路，道路是双向的，输出至少还需要修建几条，可以让所有村庄互相可达。
//一开始路为0条

//思路：直接构建并查集，输出并查集的个数

int par[100005] = {-1};//用于记录并查集的根
bool flag[100005] = {0};//用于记录并查集个数的标记

int find(int x){ //查询x所在集合的代表元，其中会进行路径压缩
    if(x == par[x])  //到达根
        return x;
    return par[x] = find(par[x]);
}

//构建并查集，并输出现阶段并查集的个数
bool unite(int a, int b){ //返回值是合并是否成功
    a = find(a); //找到代表元素
    b = find(b);
    if (a == b)   //合并失败，两个集合是同一个
        return false;
    par[a] = b ;// par[b] = a;  //合并集合，即将一个挂到另一个
    return true;
}
int main(){
    int n,m;
    //cin>>n>>m;
    scanf("%d%d",&n,&m);
    for(int i = 0; i <= n; i++)
        par[i] = i;
    int a,b;
    int num = n - 1;
    for(int i = 0; i < m; i++){
        scanf("%d%d",&a,&b);
        if(unite(a,b))
            num--;  //直接在这个地方更新num就好啦
        // for(int i = 1; i <= n; i ++){
        //     if(find(i) == i)
        //         num ++;
        // }  这个地方会导致TLE
        printf("%d\n",num);
    }
    return 0;
}

D : 网络铺设

问题描述

你现在是城市的主人 现在有n个村庄，已经修建了n-1条道路，使得各个村庄作为节点，路作为边，构成一棵树。 假设第a个村庄到第b个村庄有路相连，则从a走到b或者从b走到a需要走1m。

你需要输出n个数，第i个数代表从第i个村庄出发，距离他最远的村庄的距离

输入格式

第一行一个整数n,0≤n≤10^5 接下来有n-1行，每行a,b代表第a个村庄，到第b个村庄有一条路。 1≤a,b≤10^5

保证输入结构是一棵树

输出格式

输出一行n个数，表示答案

样例输入

5
5 1
1 2
2 3
3 4

样例输出

3 2 3 4 4

代码：

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

//你需要输出n个数，第i个数代表从第i个村庄出发，距离他最远的村庄的距离
//接下来有n-1行，每行a,b代表第a个村庄到第b个村庄有一条路。
const int maxn = 100005;

int n;
int a,b;
vector<int> v[maxn];
bool vis[maxn] = {0};
int ans = 0,ansx = -1;  //最长路径，树的直径的两个点
int dist[maxn] = {0};
int dist1[maxn] = {0};  //到点1的距离
int dist2[maxn] = {0};  //到点2的距离

void dfs(int x, int d, int *dist){
    vis[x] = 1;  //标记访问
    dist[x] = d;//max(dist[x], d); 到端点的距离
    if(d > ans){
        ans = d;
        ansx = x;
    }
    for(int i = 0; i < v[x].size(); i++ ){
        if(vis[ v[x][i] ] == 0){
            dfs(v[x][i],d+1,dist);
        }
    }
}

// void bfs(int u, int* distance) {
//     queue<int> Q;
//     Q.push(u);
//     distance[u] = 0;
//     while (!Q.empty()) {
//         int x = Q.front();
//         Q.pop();
//         vis[x] = true;
//         for (vector<int>::iterator it = v[x].begin(); it != v[x].end(); it++) {
//             int temp = *it;
//             if (!vis[temp]) {
//                 Q.push(temp);
//                 distance[temp] = distance[x] + 1;
//             }
//         }
//     }
// }

int main() {
    //scanf("%d", &n);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,0,dist);
    int ansx1 = ansx;  //记录第一个点
    ans = -1;
    ansx = -1;
    memset(vis,0,sizeof(vis));
    dfs(ansx1,0,dist1);
    int ansx2 = ansx;  //记录第二个点
    memset(vis,0,sizeof(vis));
    dfs(ansx2,0,dist2);
    for (int i = 1; i <= n; i++) {
        printf("%d ", max(dist1[i],dist2[i]));
    }
    return 0;
}

E : 水渠设计

问题描述

你现在是城市的主人 现在有n个田地需要灌溉。 可以选择修建m个引水渠，第i条从第a个田地到第b个田地，花费c元。 现在可以买任意多个抽水机，买一个抽水机需要花费p元。如果在一个田地旁边安置一个抽水机，则该田地会被灌溉。 水可以顺着水渠流动。 求让每一块田地都能被灌溉的最小花费。

输入格式

第一行三个整数 n,m,p,0≤n,m≤10^5,p≤10^9 接下来有m行，每行a,b,c代表修建了一条从第a个田地，到第b个田地的水渠，花费c 元。 1≤a,b≤n，c<=10^9

输出格式

输出一个数表示答案。

样例输入

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

样例输出

8

代码：

#include<bits/stdc++.h>
using namespace std;

//思路：考虑图重构：加一个超级源点，并向n个点连边为p，然后对n+1个点跑最小生成树
//按照边的权值增序排列，若不形成圈则加入

const int maxn = 100005;
int n,m;//现在有n个田地需要灌溉。
//可以选择修建m个引水渠，第i条从第a个田地到第b个田地，花费c元。
//买一个抽水机需要花费p元
int a,b;
long long c,p;
long long sum = 0;
int par[maxn];

struct Edge{
    int u,v;
    long long w;
};
vector<Edge> G;

bool cmp(Edge a, Edge b){
    return a.w < b.w;
}

void addEdge(int u, int v, long long w){
    Edge e;
    e.u = u;
    e.v = v;
    e.w = w;
    G.push_back(e);
    // G.emplace_back(u,v,w);
    // G.push_back({v,u,w});
}
void initial(int n){
    for(int i = 0; i <= n; i++)
        par[i] = i;
}
int find(int x){ //查询x所在集合的代表元，其中会进行路径压缩
    if(x == par[x])  //到达根
        return x;
    return par[x] = find(par[x]);
}

//构建并查集，并输出现阶段并查集的个数
bool unite(int a, int b){ //返回值是合并是否成功
    a = find(a); //找到代表元素
    b = find(b);
    if (a == b)   //合并失败，两个集合是同一个
        return false;
    par[a] = b ;// par[b] = a;  //合并集合，即将一个挂到另一个
    return true;
}
int main(){
    scanf("%d%d",&n,&m);
    cin >> p;
    initial(n);
    for(int i = 1; i <= n; i++){//加一个超级源点
        addEdge(0,i,p);   
    }
    for(int i = 0; i < m; i++){   //按照输入增加边
        scanf("%d%d",&a,&b);
        cin >> c;
        addEdge(a,b,c);
    }
    sort(G.begin(), G.begin() + m + n,cmp);   //按照边的权值大小增序排列
    for(int i = 0; i < m+n; i++){
        if(find(G[i].u) != find(G[i].v)){
            sum += G[i].w;
            unite(G[i].u,G[i].v);
        }
    }
    // for(vector<Edge>::iterator it = G.begin(); it != G.end(); it++){
    //     if(find((*it).u) != find((*it).v) ){  //若不在一个并查集中（不形成圈），则增加边
    //         sum += (*it).w;
    //         unite((*it).u, (*it).v);  //更新并查集
    //     }
    // }
    cout<<sum;
    return 0;
}

H7

A : 卖菜

问题描述

在一条街上有n个卖菜的商店，按1至n的顺序排成一排，这些商店都卖一种蔬菜。 　　第一天，每个商店都自己定了一个价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。 　　注意，编号为1的商店只有一个相邻的商店2，编号为n的商店只有一个相邻的商店n-1，其他编号为i的商店有两个相邻的商店i-1和i+1。 　　给定第一天各个商店的菜价，请计算第二天每个商店的菜价。

输入格式

输入的第一行包含一个整数n，表示商店的数量。 第二行包含n个整数，依次表示每个商店第一天的菜价。

输出格式

输出一行，包含n个正整数，依次表示每个商店第二天的菜价。

样例输入

8
4 1 3 1 6 5 17 9

样例输出

2 2 1 3 4 9 10 13

数据规模和约定

对于所有评测用例，2 ≤ n ≤ 1000，第一天每个商店的菜价为不超过10000的正整数。

代码：

//
// Created by 1341567672 on 2021/4/18.
//
#include<bits/stdc++.h>
using namespace std;

int n; //n个卖菜商店
int price1[1010] = {0};  //第一天的菜价
int price2[1010] = {0};  //第二天的菜价

int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%d",&price1[i]);

    }
    price2[1] = (price1[1] + price1[2])/2;
    price2[n] = (price1[n] + price1[n-1]) / 2;
    for(int i = 2; i < n; i++){
        price2[i] = (price1[i-1] + price1[i] + price1[i+1]) / 3;
    }
    for(int i = 1; i <= n; i++){
        printf("%d ",price2[i]);
    }
    return 0;
}

B : 买菜

问题描述

小H和小W来到了一条街上，两人分开买菜，他们买菜的过程可以描述为，去店里买一些菜然后去旁边的一个广场把菜装上车，两人都要买n种菜，所以也都要装n次车。具体的，对于小H来说有n个不相交的时间段a_1,b_1,a_2,b_2…a_n,b_n在装车，对于小W来说有n个不相交的时间段c_1,d_1,c_2,d_2…c_n,d_n在装车。其中，一个时间段[s, t]表示的是从时刻s到时刻t这段时间，时长为t-s。 由于他们是好朋友，他们都在广场上装车的时候会聊天，他们想知道他们可以聊多长时间。

输入格式

输入的第一行包含一个正整数n，表示时间段的数量。 接下来n行每行两个数a_i，b_i，描述小H的各个装车的时间段。 接下来n行每行两个数c_i，d_i，描述小W的各个装车的时间段。

输出格式

输出一行，一个正整数，表示两人可以聊多长时间。

样例输入

4
1 3
5 6
9 13
14 15
2 4
5 7
10 11
13 14

样例输出

3

数据规模和约定

对于所有的评测用例，1 ≤ n ≤ 2000, a_i < b_i < a_i+1，c_i < d_i < c_i+1,

对于所有的i(1 ≤ i ≤ n)有，1 ≤ a_i, b_i, c_i, d_i≤ 1000000。

代码：

#include<bits/stdc++.h>
using namespace std;
//两人的区间内，装车时间段分别置1，最后求两人置1区间的交集
bool time_A[1000100] = {0};
bool time_B[1000100] = {0};
int a,b,c,d;

int main(){
    int n;
    int timenum = 0;
    scanf("%d",&n);
    int a,b,c,d;
    for(int i = 1; i <= n; i++){
        scanf("%d%d",&a,&b);
        for(int j = a; j < b; j++)
            time_A[j] = 1;
    }
    for(int i = 1; i <= n; i++){
        scanf("%d%d",&c,&d);
        for(int j = c; j < d; j++)
            time_B[j] = 1;

    }
    int maxnum = max(b,d);
    for(int i = 1; i <= 1000100; i++){
        if(time_A[i] && time_B[i]) {
            timenum++;
        }
    }
    printf("%d",timenum);
    return 0;
}

C : 穿越虫洞

问题描述

小H有nn个秘密基地（编号 11 到 nn ）,nn 个秘密基地之间有 mm 条双向路径和 ww 个单向时空隧道，通过路径需要消耗一定的时间T_iT**i，而通过时空隧道可以使时光倒流T_jT**j,现在小H想知道他能否从某一秘密基地出发，通过路径和时空隧道回到过去（即回到出发的秘密基地且该时刻要早于出发时间）。

输入格式

第11行，一个整数 FF,表示测试用例的数量 接下来对于每一个测试用例，输入格式如下 第11行，三个空格分隔的整数n,m,wn,m,w 第22到 m+1m+1 行，三个空格分隔的数字 s,e,ts,e,t，表示 s,es,e 之间存在双向道路，通行需要消耗tt，允许两点间存在多条路径 第m+2m+2到m+w+1m+w+1行三个空间分隔的数字 s,e,ts,e,t,表示存在从 ss 到 ee 的单向时空隧道，穿过时空隧道时光倒流 tt

输出格式

对于每个测试用例，如果小H能回到过去则输出YES，否则输出NO 每个测试用例的输出占一行

样例输入

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

样例输出

NO
YES

数据规模和约定

1≤n≤500,1≤m≤4×10^4,1≤w≤200 1≤T_i,T_j​≤104

代码：

#include<bits/stdc++.h>
#define N 70000
#define inf 1e9
using namespace std;

int tot = 0;
int point[N],weight[N],v[N],nxt[N]; //weight权值，v到达值，
int F,n,m,w; //n个秘密基地之间有m条双向路径和w个单向时空隧道
int s,e,t;  //表示s,e之间存在双向道路,通行需要消耗t;表示存在从s到e的单向时空隧道,穿过时空隧道时光倒流t

void addA(int x,int y, int z){ //正边权
    tot++;
    nxt[tot] = point[x];
    point[x] = tot;
    v[tot] = y;
    weight[tot] = z;
    tot ++;
    nxt[tot] = point[y];
    point[y] = tot;
    v[tot] = x;
    weight[tot] = z;
}
void addB(int x,int y, int z){
    tot++;
    nxt[tot] = point[x];
    point[x] = tot;
    v[tot] = y;
    weight[tot] = -z;
}
int can[N];
int dis[N];
int cnt[N];
void spfa(int s){
    bool flag = 0;
    for(int i = 1; i <= n; i++){
        can[i] = 0;  //标记是否已到达
        dis[i] = inf;
        cnt[i] = 0;
    }
    dis[s] = 0;
    can[s] = 1;
    queue<int> p;
    p.push(s);
    while(!p.empty()){
        int now = p.front();
        p.pop();
        for(int i = point[now]; i; i = nxt[i])
            if(dis[v[i]] > dis[now] + weight[i]){
                dis[v[i]] = dis[now] + weight[i];
                cnt[v[i]] ++;
                if(cnt[v[i]] >= n){
                    //负环
                    flag = 1;
                    cout<<"YES"<<endl;
                    break;
                }
                //pre[v[i]] = now;
                if(!can[v[i]]){
                    can[v[i]] = 1;
                    p.push(v[i]);
                }
            }
        can[now] = 0;
        if(flag)
            break;
    }
    if(!flag)
        cout<<"NO"<<endl;
}


int main(){
    scanf("%d",&F);
    for(int i = 0; i < F; i++){
        scanf("%d%d%d",&n,&m,&w);
        for(int i=1;i<=n;i++)
        {
            point[i]=0;
            v[i]=0;
            nxt[i]=0;
            weight[i]=0;
        }
        for(int j = 2; j <= m + 1; j ++){
            scanf("%d%d%d",&s,&e,&t);
            addA(s,e,t);
        }
        for(int j = m+2; j <= m + w + 1; j++){
            scanf("%d%d%d",&s,&e,&t);
            addB(s,e,t);
        }
        
        spfa(1);
        tot = 0;
    }
    return 0;
}

D : 差旅花费

问题描述

有n个车站，其中1号车站为始发站，现有n-1个人，你需要安排他们分别去往除始发站以外的n-1个车站，然后返回始发站。交通系统的所有路径均为单向路径，连接两个不同的车站，每经过一条路径需要交纳一定的费用，你能求出总花费的最低金额嘛

输入格式

第一行一个整数T，表示测试用例的个数。 对于每个测试用例，输入格式如下 第一行两个整数n,m,分别表示车站的数量和车站之间的单向路径数。 接下来m行，每行三个数s,e,c,表示存在从s到e的单向路径，花费为c

输出格式

对于每个测试用例，输出其总花费的最低金额，每个测试用例的输出占一行。

样例输入

2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

样例输出

46
210

数据规模和约定

1<=n,m<=1000000 价格c为正整数，且保证其总和小于1000000000

代码：

#include<bits/stdc++.h>
#define N 2000100
#define inf 1e9
using namespace std;
//有n个车站，其中1号车站为始发站，现有n-1个人，
// 你需要安排他们分别去往除始发站以外的n-1个车站，然后返回始发站。
// 交通系统的所有路径均为单向路径，连接两个不同的车站，每经过一条路径需要交纳一定的费用，你能求出总花费的最低金额嘛
//第一行一个整数T，表示测试用例的个数。
//第一行两个整数n,m,分别表示车站的数量和车站之间的单向路径数。
//接下来m行，每行三个数s,e,c,表示存在从s到e的单向路径，花费为c

//思路：求1到所有点的最短路径之和以及所有点到1（把边反着建，即将u和v对调）的最短路之和
int T;
int n,m;
int s,e,c;
int point1[N],v1[N],nxt1[N],weight[N];
int point2[N],v2[N],nxt2[N];
int dis[N],vis[N];
int tot = 0;
void add(int x,int y, int z){
    tot++;
    nxt1[tot] = point1[x]; point1[x] = tot; v1[tot] = y;
    nxt2[tot] = point2[y]; point2[y] = tot; v2[tot] = x;
    weight[tot] = z;}
void dijkstra1(int s){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>> > q1;
    for(int i = 1; i <= N; i++)
        dis[i] = inf, vis[i] = 0;
    dis[s] = 0;
    q1.push(make_pair(0,s));
    while(!q1.empty()){
        int x = q1.top().second;
        q1.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = point1[x]; i; i = nxt1[i])
            if(dis[v1[i]] > dis[x] + weight[i]){
                dis[v1[i]] = dis[x] + weight[i];
                q1.push(make_pair(dis[v1[i]],v1[i]));
            }
    }
}
void dijkstra2(int s){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>> > q2;
    for(int i = 1; i <= N; i++)
        dis[i] = inf, vis[i] = 0;
    dis[s] = 0;
    q2.push(make_pair(0,s));
    while(!q2.empty()){
        int x = q2.top().second;
        q2.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = point2[x]; i; i = nxt2[i])
            if(dis[v2[i]] > dis[x] + weight[i]){
                dis[v2[i]] = dis[x] + weight[i];
                q2.push(make_pair(dis[v2[i]],v2[i]));
            }
    }
}
int main(){
    scanf("%d",&T);
    for(int i = 0; i < T; i++){
        long long sum = 0;
        scanf("%d%d",&n,&m);
        tot = 0;
        for(int i = 1; i <= N; i++){
            point1[i] = 0, point2[i] = 0,
            v1[i] = 0, v2[i] = 0;
            nxt1[i] = 0, nxt2[i] = 0;
            weight[i] = 0;
        }
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d",&s,&e,&c);
            add(s,e,c);
        }
        dijkstra1(1);
        for(int i = 2; i <= n; i++)
            sum += (long long)dis[i];
        dijkstra2(1);
        for(int i = 2; i <= n; i++)
            sum += (long long)dis[i];
        printf("%lld\n",sum);
    }
//    system("pause");
    return 0;
}

E : 运输货物

问题描述

考虑一个具有N个顶点，M条边的无向图。编号为1的顶点对应于一个矿山，从中提取一些珍贵的矿物。编号为N的顶点对应于一家矿物加工厂。每条边连接两个不同的顶点并拥有有两个参数，分别为最大承重量C和通行时间D。现在将从矿山中提取的矿物并选择一条路径将提取的矿物运送至工厂。该路径应具有最大的承重量，以便能够同时运输尽可能多的矿物。路径的承重量等于路径中经过的边的最大承重量的最小值。但是，这些矿物非常敏感，一旦从矿山中提取出来，它们将在T时间单位后开始分解，除非他们在此时间间隔内到达工厂。因此，所选路径的总行进时间（其路径的通行时间之和）应小于或等于T。

输入格式

输入的第一行包含一个整数X，表示测试用例的数量。 每个测试用例的第一行包含3个整数，并用空格分隔：N，M，T。接下来的M行中的每行将包含四个整数，每个数字用空格分隔：A，B，C和D，这意味着顶点A和B之间存在一条边，最大承重量为C，通行时间为D。A和B是1和N之间的不同整数。任何两个顶点之间最多存在一个边。

输出格式

对于X个测试用例，请输出在满足通行时间限制下的路径最大承重量，每个测试用例对应一行。 数据保证图中至少存在一条1到n通行总时间小于等于T的路径，即一定有解。

样例输入

2
2 1 10
1 2 13 10
4 4 20
1 2 1000 15
2 4 999 6
1 3 100 15
3 4 99 4

样例输出

13
99

数据规模和约定

1≤𝑛≤10000， 1≤m≤50000，1≤𝑇≤500000 1≤𝐶≤10000000， 1≤𝐷≤50000

代码：

#include<bits/stdc++.h>
#define maxN 10010
#define inf 1e9
using namespace std;
// N个顶点，M条边的无向图
// 顶点A、B分别为最大承重量C和通行时间D
// 总行进时间（其路径的通行时间之和）应小于或等于T。
int X,N,M,T;
int A,B,C,D;
//int point[maxN],v[maxN],nxt[maxN],c[maxN],d[maxN]; //weight权值，v到达值，
int vis[maxN];
int dis[maxN];
int tot = 0;
struct Edge{
    int v,c,d;
};
vector<Edge> vinit[maxN];
vector<Edge> vnew[maxN];

void dijkstra(int s,int cc){
    for(int i = 1; i <= N; i++){
        vnew[i].clear();
    }
    for(int i = 1; i <= N; i++){
        for(vector<Edge>::iterator it = vinit[i].begin(); it != vinit[i].end(); it++){
            if((*it).c >= cc){
                vnew[i].push_back(*it);
                Edge E = *it;
                int u = E.v;
                E.v = i;
                vnew[u].push_back(E);
            }

        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    for(int i = 1; i <= N; i++)
        dis[i] = INT_MAX, vis[i] = 0;
    dis[s] = 0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int x = q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = 0; i < vnew[x].size(); i++ ){
            int now = vnew[x][i].v;
            if(dis[now] > dis[x] + vnew[x][i].d){
                dis[now] = dis[x] + vnew[x][i].d;
                q.push(make_pair(dis[now],now));
            }
        }
    }
}
int main(){
    scanf("%d",&X);
    for(int i = 0; i < X; i++){
        scanf("%d%d%d",&N,&M,&T);
        for(int j = 1; j <= N; j++)
            vinit[j].clear();
        for(int j = 0; j < M; j++){
            scanf("%d%d%d%d",&A,&B,&C,&D);
            Edge E;
            E.v = B; E.c = C; E.d = D;
            vinit[A].push_back(E);
            E.v = A;
            vinit[B].push_back(E);
        }
        int minC = 0;
        int maxC = 10000000;
        int midC ;
        while(minC < maxC){
            midC = (maxC+minC)>>1;
            dijkstra(1,midC);
            if(dis[N] > T)
                maxC = midC;
            else
                minC = midC + 1 ;
        }
        printf("%d\n",minC - 1);
    }
}

#include<bits/stdc++.h>
#define maxN 1001000
#define inf 1e9
using namespace std;
// N个顶点，M条边的无向图
// 顶点A、B分别为最大承重量C和通行时间D
// 总行进时间（其路径的通行时间之和）应小于或等于T。
long long X,N,M,T;
int A,B;
long long C,D;
int point[maxN],v[maxN],nxt[maxN];
long long c[maxN],d[maxN]; //weight权值，v到达值，
int vis[maxN];
long long dis[maxN];
long long tot = 0;
//priority_queue<pair<int,int>,vector<pair<int,int> > > q;
void add(int x1, int x2, long long x3, long long x4){
    tot++;
    nxt[tot] = point[x1];
    point[x1] = tot;
    v[tot] = x2;
    c[tot] = x3;
    d[tot] = x4;
    tot ++;
    nxt[tot] = point[x2];
    point[x2] = tot;
    v[tot] = x1;
    c[tot] = x3;
    d[tot] = x4;
}
void dijkstra(int s,int cc){
    priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q;
    for(int i = 1; i <= N; i++)
        dis[i] = INT_MAX, vis[i] = 0;
    dis[s] = 0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int x = q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = point[x]; i; i = nxt[i])
            if(dis[v[i]] > dis[x] + d[i] && c[i] >= cc){
                dis[v[i]] = dis[x] + d[i];
                q.push(make_pair(dis[v[i]],v[i]));
            }
    }
}
int main(){
    scanf("%lld",&X);
    for(int i = 0; i < X; i++){
        scanf("%lld%lld%lld",&N,&M,&T);
        for(int j = 0; j <= maxN; j++){
            nxt[j] = 0; point[j] = 0; v[j] = 0; c[j] = 0; d[j] = 0;
        }
        tot = 0;
        for(int j = 0; j < M; j++){
            scanf("%d%d%lld%lld",&A,&B,&C,&D);
            add(A,B,C,D);
        }
        int minC = 0;
        int maxC = 10000000;
        int midC;
        while(minC < maxC){
            midC = (maxC+minC)>>1;
            dijkstra(1,midC);
            if(dis[N] > T)
                maxC = midC;
            else
                minC = midC + 1 ;
        }
        printf("%d\n",minC-1);
    }
}

H8

A : 元音回文

问题描述

现在有一个长度为 nn 的字符串，都有小写字母组成。 现在所有元音字母都可以看作相同的字符 输出最长回文子串的长度

一个与自身的逆序相同的字符串即为回文串 比如 aba,aabbaa,asdffdsa都为回文串

输入格式

第一行一个整数 n,1≤n≤5000，表示字符串长度 接下来一行表示字符串

输出格式

输出一行，一个数，代表答案

样例输入

10
aeioubaeio

样例输出

9

样例解释

所以元音都可以看作相同字符，所以回文串为 eioubaeio

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int length = 0;
//现在有一个长度为n的字符串，都有小写字母组成。
//现在所有元音字母都可以看作相同的字符
//输出最长回文子串的长度
int main(){
    scanf("%d",&n);
    getchar();
    char *c = new char[n];
    for(int i = 0; i < n; i++){
        scanf("%c",&c[i]);
        if(c[i] == 'a' || c[i] == 'e' || c[i] == 'i' || c[i] == 'o' || c[i] == 'u')
            c[i] = 'a';
    }
    for(int i = 1; i < n; i++){
        if(c[i] == c[i-1]){
            int templength = 0;
            for(int l = i - 1, r = i ; l >= 0 && r < n; l--, r++){
                if(c[l] == c[r])
                    templength += 2;
                else
                    break;
            }
            length = max(length,templength);
        }
        if(c[i-1] == c[i+1]){
            int templength = 1;
            for(int l = i - 1, r = i + 1; l >= 0 && r < n; l--, r++){
                if(c[l] == c[r])
                    templength +=2;
                else
                    break;
            }
            length = max(length,templength);
        }
    }
    printf("%d\n",length);
}

B : 模测成绩单

问题描述

模测结束了，小 L 拿到了一些形如A 比 B 得分高 的信息，现在小 L 想要输出一份成绩排名表，使得排名表满足得到的信息，并且学号小的尽可能排在前面。

输入格式

第一行有两个整数，n,m表示有n个同学，第i个同学学号为i，有m条信息。 接下来有m行，每行有两个整数A,B，表示学号为A的同学得分比学号为B的同学得分高。 1≤n,m≤10^6 1≤A,B≤n 数据保证有解

输出格式

输出一行n个数，表示按照学号给出的排名。

样例输入

5 3
4 5
2 3
1 5

样例输出

1 2 3 4 5

代码：

#include<bits/stdc++.h>
using namespace std;
//第一行有两个整数，n,m表示有 n个同学，第i个同学学号为i，有m条信息。
//接下来有m行，每行有两个整数A,B，表示学号为A的同学得分比学号为B的同学得分高。
int n,m;
int A,B;
int in_deg[1000100] = {0};
struct Edge{
    int u,v;
    Edge(int a,int b){u = a;v = b;}
};
vector<int> v[1000100];

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; i++){
        scanf("%d%d",&A,&B);
        in_deg[B] ++;
        Edge e(A,B);
        v[A].push_back(B);
    }
    priority_queue<int,vector<int>,greater<int> > q;//保证学号小的尽可能在前面
    for(int i = 1; i <= n; i++){
        if(in_deg[i] == 0)
            q.push(i);
    }
    vector<int> ans;
    while(!q.empty()){
        int tempu = q.top();
        q.pop();
        ans.push_back(tempu);
        for(int i = 0; i < v[tempu].size(); i++){
            if( --in_deg[v[tempu][i]] == 0)
                q.push(v[tempu][i]);
        }
    }
    for(int i = 0; i < n; i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

C : 种酸奶

问题描述

小 L 喜欢喝酸奶，春天来了，小 L 想把酸奶种在地里，等到来年春暖花开，就能长出好多好多酸奶了 有n个坑，小L给坑都编上号，从 11 号到n号，每个坑最多种一瓶酸奶。 但是有一些限制形如 k,a,b,c。 若 k 等于 1 ，则第 a 号坑到第 b 号坑最多种 c 瓶酸奶。 若 k 等于 2 ，则第 a 号坑到第 b 号坑最少种 c 瓶酸奶。 若 k 等于 3 ，则第 a 号坑到第 b 号坑必须种少于 c 瓶酸奶。 若 k 等于 4 ，则第 a 号坑到第 b 号坑必须种多于 c 瓶酸奶。 若 k 等于 5 ，则第 a 号坑到第 b 号坑必须种等于 c 瓶酸奶。

问小 L 最多种多少瓶酸奶

输入格式

第一行两个整数 n,m，表示有 n 个坑，有 m 条限制。 1≤n,m≤1000 接下来 m 行，每行四个整数 k,a,b,c 1≤k≤5, 1≤a≤b≤n , |c|<=2000

输出格式

输出一行，若有解则输出一个整数，表示答案 否则输出 impossible

样例输入

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

样例输出

3

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxN 1010
#define inf 100000000
//小 L 喜欢喝酸奶，春天来了，小 L 想把酸奶种在地里，等到来年春暖花开，就能长出好多好多酸奶了
//有 n 个坑，小 L 给坑都编上号，从 11 号到 nn 号，每个坑最多种一瓶酸奶。
//但是有一些限制形如 k,a,b,c
//若 k 等于 1 ，则第 a 号坑到第 b 号坑最多种 c 瓶酸奶。 s[b]-s[a-1]<= c
//若 k 等于 2 ，则第 a 号坑到第 b 号坑最少种 c 瓶酸奶。  s[b]-s[a-1]>=c..s[a-1]-s[b]<=-c
//若 k 等于 3 ，则第 a 号坑到第 b 号坑必须种少于 c 瓶酸奶。 s[b]-s[a-1]<c..s[b]-s[a-1]<=c-1
//若 k 等于 4 ，则第 a 号坑到第 b 号坑必须种多于 c 瓶酸奶。 s[b]-s[a-1]>c..s[a-1]-s[b]<=-c-1
//若 k 等于 5 ，则第 a 号坑到第 b 号坑必须种等于 c 瓶酸奶。 s[b]-s[a-1]<=c s[b]-s[a-1]>=c..s[a-1]-s[b]<=-c
//0<=s[i]-s[i-1]<=1
//问小 L 最多种多少瓶酸奶   1到n的最长路径

int n,m; //n个坑，m条限制
int k,a,b;
long long c;  //m行
long long dis[maxN];
int vis[maxN];
int cnt[maxN];
struct Edge{
    int v; //到达点
    long long w; //权重
    Edge(int vv,long long ww){v = vv; w = ww;}
};
vector<Edge> ev[maxN];

bool spfa(int s){
    for(int i = 0; i < maxN; i++)
        dis[i] = inf, vis[i] = 0, cnt[i] = 0;
    dis[s] = 0;
    vis[s] = 1;
    queue<int> p;
    p.push(s);
    while(!p.empty()){
        int now = p.front();
        p.pop();
        for(int i = 0; i < ev[now].size(); i++){
            if(dis[ev[now][i].v] > dis[now] + ev[now][i].w){
                dis[ev[now][i].v] = dis[now] + ev[now][i].w;
                cnt[ev[now][i].v] ++;
                if(cnt[ev[now][i].v] >= n)
                    return false;
                if(!vis[ev[now][i].v]){
                    vis[ev[now][i].v] = 1;
                    p.push(ev[now][i].v);
                }
            }
        }
        vis[now] = 0;
    }
    return true;
}


int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; i++){
        scanf("%d%d%d%lld",&k,&a,&b,&c);
        if(k == 1){
            Edge e(b,c);
            ev[a-1].push_back(e);
        }
        if(k == 2){
            Edge e(a-1,-c);
            ev[b].push_back(e);
        }
        if(k == 3){
            Edge e(b,c-1);
            ev[a-1].push_back(e);
        }
        if(k == 4){
            Edge e(a-1,-c-1);
            ev[b].push_back(e);
        }
        if(k == 5) {
            Edge e1(b,c);
            ev[a-1].push_back(e1);
            Edge e2(a-1,-c);
            ev[b].push_back(e2);
        }
    }
    for(int i = 1; i <= n; i++){
        Edge e1(i-1,0);
        Edge e2(i,1);
        ev[i].push_back(e1);
        ev[i-1].push_back(e2);
    };
    if(spfa(0)){
        if(dis[n] != inf )
            printf("%lld\n",dis[n]);}
    else
        printf("impossible");
    return 0;
}

D : 信息传递

问题描述

有 n 个人，每个人都有一个编号，从 1 到 n 。 如果 A 得知一个消息，那么他一定会告诉 B 。 问最少把消息告诉几个人，能让所有人得知这个消息。

输入格式

第一行两个整数 n,m , 1≤n,m≤10^6，表示有 n个人 接下来 m行，每行给出一个关系形如 A,B，表示如果A得知一个消息，那么他一定会告诉B。

输出格式

输出一行，一个数，代表答案

样例输入

10 10
1 3
2 4
4 5
2 8
5 2
5 9
6 8
9 2
10 5
5 8

样例输出

4  

样例解释

只需要告诉 1,6,7,10 四个人即可

代码：

//构建原图与反图
#include<bits/stdc++.h>
using namespace std;
#define maxN 1000100
//有 nn 个人，每个人都有一个编号，从 11 到 nn 。
//如果 AA 得知一个消息，那么他一定会告诉 BB 。
//问最少把消息告诉几个人，能让所有人得知这个消息。
int n,m;
int A,B;
int vis[maxN],c[maxN],dfn[maxN],dcnt,scnt; //dcnt-dfs序计数，scnt-scc计数，dfn[i]-dfs后序列中第i个点，c[i]-i号点所在SCC编号
bool flag[maxN]; //记录每个连通分量入度是否为0
vector<int> G1[maxN];
vector<int> G2[maxN]; //反图
int indegree[maxN] = {0};

void dfs1(int x){
    vis[x] = 1;
    for(int i = 0; i < G1[x].size(); i++){
        if(!vis[G1[x][i]])
            dfs1(G1[x][i]);
    }
    dfn[++dcnt] = x;//dfn[i]-dfs后序列中第i个点
}

void dfs2(int x){
    c[x] = scnt;
    for(int i = 0; i < G2[x].size(); i++){
        if(!c[G2[x][i]])
            dfs2(G2[x][i]);
    }
}

void kosaraju(){
    //初始化
    dcnt = scnt = 0;
    memset(c,0,sizeof c);
    memset(vis, 0, sizeof vis);
    //第一遍dfs  记录每个点是dfs之后 dfs中的第几个点
    for(int i = 1; i <= n; i++)
        if(!vis[i]) dfs1(i);
    //第二遍dfs  记录所在的SCC编号
    for(int i = n; i >= 1; i--)
        if(!c[dfn[i]]) ++scnt,dfs2(dfn[i]);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; i++){
        scanf("%d%d",&A,&B);
        G1[A].push_back(B);
        G2[B].push_back(A);
    }
    kosaraju();
    for(int i = 1; i <= scnt; i++)
        flag[i] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < G1[i].size(); j++){
            if(c[i] != c[G1[i][j]])
                flag[c[G1[i][j]]] = 1;
        }
    }
    int ans = 0;
    for(int i = 1; i <= scnt; i++)
        if(!flag[i])
            ans++;
    printf("%d\n",ans);
    return 0;
}

H9

A : 化学方程式

题目描述

化学方程式，也称为化学反应方程式，是用化学式表示化学反应的式子。给出一组化学方程式，请你编写程序判断每个方程式是否配平（也就是方程式中等号左右两边的元素种类和对应的原子个数是否相同)。

本题给出的化学方程式由大小写字母、数字和符号（包括等号=、加号+、左圆括号(和右圆括号))组成，不会出现其他字符（包括空白字符，如空格、制表符等)。化学方程式的格式与化学课本中的形式基本相同（化学式中表示元素原子个数的下标用正常文本，如 H_2O写成 H2O)，用自然语言描述如下:

• 化学方程式由左右两个表达式组成，中间用一个等号=连接，如2H2+O2=2H2O；

• 表达式由若干部分组成，每部分由系数和化学式构成，部分之间用加号+连接,如2H2+O2、2H2O；

• 系数是整数或空串，如为空串表示系数为 11；

• 整数由一个或多个数字构成；

• 化学式由若干部分组成，每部分由项和系数构成，部分之间直接连接，如H2O、CO2、Ca(OH)2、Ba3(PO4)2；

• 项是元素或用左右圆括号括起来的化学式，如 H、Ca、(OH)、(PO4):

• 元素可以是一个大写字母，也可以是一个大写字母跟着一个小写字母，如H、O、Ca。

用巴科斯范式(Backus-Naur form，BNF)给出的形式化定义如下：

<equation> ::= <expr> "=" <expr>
<expr> ::= <coef> <formula> | <expr> "+" <coef> <formula>
<coef> ::= <digits> | ""
<digits> ::= <digit> | <digits> <digit>
<digit> ::= "0" | "1" | ... | "9"
<formula> ::= <term> <coef> | <formula> <term> <coef>
<term> ::= <element> | "(" <formula> ")"
<element> ::= <uppercase> | <uppercase> <lowercase>
<uppercase> ::= "A" | "B" | ... | "Z"
<lowercase> ::= "a" | "b" | ... | "z"

输入格式

从标准输入读入数据。 输入的第一行包含一个正整数n，表示输入的化学方程式个数。接下来 n 行，每行是一个符合定义的化学方程式。

输出格式

输出到标准输出。 输出共 n 行，每行是一个大写字母 Y 或 N，回答输入中相应的化学方程式是否配平。

子任务

• 1≤n≤100

• 输入的化学方程式都是符合题目中给出的定义的，且长度不超过 10001000

• 系数不会有前导零，也不会有为零的系数

• 化学方程式的任何一边，其中任何一种元素的原子总个数都不超过 10^9109

测试点编号	满足条件
1,21,2	只包含大写字母和等号
3,43,4	加入小写字母和加号
5,65,6	加入数字
7,87,8	加入圆括号，圆括号不会出现嵌套
9,109,10	圆括号可以出现嵌套

Input

11
H2+O2=H2O
2H2+O2=2H2O
H2+Cl2=2NaCl
H2+Cl2=2HCl
CH4+2O2=CO2+2H2O
CaCl2+2AgNO3=Ca(NO3)2+2AgCl
3Ba(OH)2+2H3PO4=6H2O+Ba3(PO4)2
3Ba(OH)2+2H3PO4=Ba3(PO4)2+6H2O
4Zn+10HNO3=4Zn(NO3)2+NH4NO3+3H2O
4Au+8NaCN+2H2O+O2=4Na(Au(CN)2)+4NaOH
Cu+As=Cs+Au

Output

N
Y
N
Y
Y
Y
Y
Y
Y
Y
N

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
struct element_set{ //存储元素的集合
    map <string, int> mp;
    bool operator == (const element_set &t) const{
        return mp == t.mp;
    }
    void operator += (const element_set &t) {
        for(auto &x:t.mp) mp[x.first] += x.second;
    }
    void operator *= (const int v){
        for(auto &x:mp) x.second *= v;
    }
};

vector<string> split(const string &s, char c){ //字符串分割
    vector<string> ans;
    string temp;
    for(auto x:s){
        if(x == c){
            if(!temp.empty()) ans.emplace_back(temp), temp = "";
        }
        else temp += x;
    }
    if(!temp.empty()) ans.emplace_back(temp),temp = "";
    return ans;
}
//读一个数字
int read_int(string &s, int &p){
    int res = 0;
    while(p < s.length() && isdigit(s[p]))
        res = res*10 +s[p] -'0',p++;
    if(res == 0) return 1;
    return res;
}
//读一个元素
string read_element(string &s, int &p){
    string ans;
    if(isupper(s[p]))
        ans += s[p],p++;
    if(islower(s[p]))
        ans += s[p],p++;
    return ans;
}

//递归下降法，解析字符串元素，传字符串的引用和位置的引用
element_set str2set(string &s, int &p){
    element_set ans;
    int multi = read_int(s,p);
    while(p < s.length()){
        if(s[p] == '('){  //左括号递归
            ++p;
            ans += str2set(s,p);
        }else if(s[p] == ')'){ //右括号，处理完当前退出
            ++p;
            ans *= read_int(s,p);
            return ans;
        }
        else{
            string tmp = read_element(s,p);
            ans.mp[tmp] += read_int(s,p);
        }
    }
    ans *= multi;
    return ans;
}

bool judge(string &s){
    vector<string> left_right_s = split(s,'='); //用等号将其分为两个字符串
    element_set ans[2];
    for(int i = 0; i<= 1; i++){
        vector<string> el = split(left_right_s[i],'+'); //用加号分别分割等号左右两边的字符串
        for(int j = 0, p = 0; j < el.size(); j ++, p = 0){
            ans[i] += str2set(el[j],p); //对每一个化学式及其系数的处理
        }
    }
    return ans[0] == ans[1];
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        if(judge(s))
            printf("Y\n");
        else
            printf("N\n");
    }
    return 0;
}

B : 带配额的文件系统

题目背景

小 H 同学发现，他维护的存储系统经常出现有人用机器学习的训练数据把空间占满的问题，十分苦恼。 查找了一阵资料后，他想要在文件系统中开启配额限制，以便能够精确地限制大家在每个目录中最多能使用的空间。

文件系统概述

文件系统，是一种树形的文件组织和管理方式。在文件系统中，文件是指用名字标识的文件系统能够管理的基本对象，分为普通文件和目录文件两种，目录文件可以被简称为 目录。目录中有一种特殊的目录被叫做 根目录。

除了根目录外，其余的文件都有名字，称为文件名。合法的文件名是一个由若干数字（[0-9]）、大小写字母（[A-Za-z]）组成的非空字符串。普通文件中含有一定量的数据，占用存储空间；目录不占用存储空间。

文件和目录之间存在含于关系。上述概念满足下列性质：

1. 有且仅有一个根目录；

2. 对于除根目录以外的文件，都含于且恰好含于一个目录；

3. 含于同一目录的文件，它们的文件名互不相同；

4. 对于任意不是根目录的文件 ff，若 ff 不含于根目录，那么存在有限个目录 d_1, d_2, \dots, d_nd1,d2,…,d**n，使得 ff 含于 d_1d1，d_1d1 含于 d_2d2，\dots…，d_nd**n 含于根目录。

结合性质 4 和性质 2 可知，性质 4 中描述的有限多个目录，即诸 d_id**i ，是唯一的。再结合性质 3，我们即可通过从根目录开始的一系列目录的序列，来唯一地指代一个文件。

我们记任意不是根目录且不含于根目录的文件 ff 的文件名是 N_fN**f，那么 ff 的路径是：‘/’ + N{d_n} + ‘/’ + \dots + N{d_1} + ‘/’ + N_f‘/’+Ndn+‘/’+⋯+N**d1+‘/’+N**f，其中符号 ++ 表示字符串的连接；对于含于根目录的文件 ff，它的路径是：‘/’ + N_f‘/’+N**f；根目录的路径是：‘/’‘/’。不符合上述规定的路径都是非法的。

例如：/A/B/A/B 是合法路径，但 /A//B/A//B、/A//A/、A/A/、A/BA/B 都不是合法路径。

若文件 ff 含于目录 dd，我们也称 ff 是 dd 的孩子文件。dd 是 ff 的双亲目录。我们称文件 ff 是目录 dd 的后代文件，如果满足：(1) ff 是 dd 的孩子文件，或 (2) ff 含于 dd 的后代文件。

如图所示，该图中绘制的文件系统共有 8 个文件。其中，方形表示目录文件，圆形表示普通文件，它们之间的箭头表示含于关系。在表示文件的形状上的文字是其文件名；各个形状的左上方标记了序号，以便叙述。

在该文件系统中，文件 5 含于文件 2，文件 5 是文件 2 的孩子文件，文件 5 也是文件 2 的后代文件。文件 8 是文件 2 的后代文件，但不是文件 2 的孩子文件。文件 8 的路径是 /D1/D1/F2/D1/D1/F2。

配额概述

配额是指对文件系统中所含普通文件的总大小的限制。对于每个目录 dd，都可以设定两个配额值：目录配额 和 后代配额。

我们称目录配额 LD_dLDd 是满足的，当且仅当 dd 的孩子文件中，全部普通文件占用的存储空间之和不大于该配额值。我们称后代配额 LR_dLRd 是满足的，当且仅当 dd 的后代文件中，全部普通文件占用的存储空间之和不大于该配额值。我们称文件系统的配额是满足的，当且仅当该文件系统中所有的配额都是满足的。

很显然，若文件系统中仅存在目录，不存在普通文件，那么该文件系统的配额一定是满足的。随着配额和文件的创建，某个操作会使文件系统的配额由满足变为不满足，这样的操作会被拒绝。例如：试图设定少于目前已有文件占用空间的配额值，或者试图创建超过配额值的文件。

题目描述

在本题中，假定初始状态下，文件系统仅包含根目录。你将会收到若干对文件系统的操作指令。对于每条指令，你需要判断该指令能否执行成功，对于能执行成功的指令，在成功执行该指令后，文件系统将会被相应地修改。对于不能执行成功的指令，文件系统将不会发生任何变化。你需要处理的指令如下：

创建普通文件

创建普通文件指令的格式如下：

C <file path> <file size>

创建普通文件的指令有两个参数，是空格分隔的字符串和一个正整数，分别表示需要创建的普通文件的路径和文件的大小。

对于该指令，若路径所指的文件已经存在，且也是普通文件的，则替换这个文件；若路径所指文件已经存在，但是目录文件的，则该指令不能执行成功。

当路径中的任何目录不存在时，应当尝试创建这些目录；若要创建的目录文件与已有的同一双亲目录下的孩子文件中的普通文件名称重复，则该指令不能执行成功。

另外，还需要确定在该指令的执行是否会使该文件系统的配额变为不满足，如果会发生这样的情况，则认为该指令不能执行成功，反之则认为该指令能执行成功。

移除文件

移除文件指令的格式如下：

R <file path>

移除文件的指令有一个参数，是字符串，表示要移除的文件的路径。

若该路径所指的文件不存在，则不进行任何操作。若该路径所指的文件是目录，则移除该目录及其所有后代文件。在上述过程中被移除的目录（如果有）上设置的配额值也被移除。

该指令始终认为能执行成功。

设置配额值

Q <file path> <LD> <LR>

设置配额值的指令有三个参数，是空格分隔的字符串和两个非负整数，分别表示需要设置配额值的目录的路径、目录配额和后代配额。

该指令表示对所指的目录文件，分别设置目录配额和后代配额。若路径所指的文件不存在，或者不是目录文件，则该指令执行不成功。

若在该目录上已经设置了配额，则将原配额值替换为指定的配额值。

特别地，若配额值为 0，则表示不对该项配额进行限制。若在应用新的配额值后，该文件系统配额变为不满足，那么该指令执行不成功。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 nn，表示需要处理的指令条数。 输入接下来会有 nn 行，每一行一个指令。指令的格式符合前述要求。

输入数据保证：对于所有指令，输入的路径是合法路径；对于创建普通文件和移除文件指令，输入的路径不指向根目录。

输出格式

输出到标准输出。

输出共有 nn 行，表示相应的操作指令是否执行成功。若成功执行，则输出字母 Y；否则输出 N。

样例解释

样例1

输入总共有 10 条指令。

其中前两条指令可以正常创建两个普通文件。

第三条指令试图创建 /A/B/1/3，但是 /A/B/1 已经存在，且不是目录，而是普通文件，不能再进一步创建孩子文件，因此执行不成功。

第四条指令试图创建 /A，但是 /A 已经存在，且是目录，因此执行不成功。

第五条指令试图删除 /A/B/1/3，由于该文件不存在，因此不对文件系统进行修改，但是仍然认为执行成功。

第六条指令试图在根目录增加后代配额限制，但此时，文件系统中的文件总大小是 2048，因此该限制无法生效，执行不成功。

第七条指令试图创建文件 /A/B/1，由于 /A/B/1 已经存在，且是普通文件，因此该指令实际效果是 将原有的该文件替换。此时文件总大小是 1124，因此第八条指令就可以执行成功了。

第九条指令递归删除了 /A/B 目录和它的所有后代文件。此时文件系统中已经没有普通文件，因此第十条命令可以执行成功。

样例2

输入共有 9 条指令。

第一条指令试图为 /A/B 创建配额规则，然而该目录并不存在，因此执行不成功。

接下来的两条指令创建了两个普通文件。

再接下来的两条指令分别在目录 /A/B 和 /A/C 创建了两个配额规则。其中前者是目录配额，后者是后代配额。

接下来的两条指令，创建了两个文件。其中，/A/B/3 超出了在 /A/B 的目录配额，因此执行不成功；但 /A/B/D/3 不受目录配额限制，因此执行成功。

最后两条指令，创建了两个文件。虽然在 /A/C 没有目录配额限制，但是无论是 /A/C 下的孩子文件还是后代文件，都受到后代配额的限制，因此两条指令执行都不成功。

子任务

本题目各个测试点的数据规模如下：

表格中，目录层次是指各指令中出现的路径中，/ 字符的数目。

所有输入的数字均不超过 10^{18}1018。

Input

10
C /A/B/1 1024
C /A/B/2 1024
C /A/B/1/3 1024
C /A 1024
R /A/B/1/3
Q / 0 1500
C /A/B/1 100
Q / 0 1500
R /A/B
Q / 0 1

Output

Y
Y
N
N
Y
N
Y
Y
Y
Y

Input

9
Q /A/B 1030 2060
C /A/B/1 1024
C /A/C/1 1024
Q /A/B 1024 0
Q /A/C 0 1024
C /A/B/3 1024
C /A/B/D/3 1024
C /A/C/4 1024
C /A/C/D/4 1024

Output

N
Y
Y
Y
Y
N
Y
N
N

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pn (cout << "N\n")
#define py (cout << "Y\n")

struct file{
    int file_type; //0普通文件 1目标文件
    ll file_size;
    ll all_mx, son_mx; //目录配额，后代配额
    ll all_used, son_used; //当前大小
    map<string, file *> ch;

    file(int type, ll size = 0):
        file_type(type), file_size(size), all_mx(0), son_mx(0), all_used(0), son_used(0){}
    ~file(){
        for(auto &it:ch) delete it.second;
    }
    //预分配
    bool pre_add_size(ll size, bool last = false) const{
        if(all_mx && all_used + size > all_mx) return false; //已经使用的加上预分配的大于最大值那么不合法
        if(last && son_mx && son_used + size > son_mx) return false;
        return true;
    }
    //实际分配
    void add_size(ll size, bool last = false){
        if(last) son_used += size; //是最后一个元素
        all_used += size;
    }
    //获取节点大小
    ll get_size() const{
        if(file_type == 0) return file_size; //普通文件
        return all_used; //目录文件
    }
    //设置配额
    bool set_size(ll all, ll son){
        if((all && all_used > all) || (son && son_used > son))  //不符合设置配额的条件
            return false;
        all_mx = all, son_mx = son;
        return true;
    }
};

struct fileSystem{
    file *root; //根目录
    vector<string> path;
    string filename;

    fileSystem(){
        root = new file(1);
    }
    ~fileSystem(){delete root;}

    void set_path(string &pa){//设置目录路径
        path.clear(); //之前的目录清空
        string tmp;
        for(auto c:pa){  //依次读入
            if(c =='/'){ //遇到分隔符，将其压入路径并清空
                if(!tmp.empty()) path.emplace_back(tmp), tmp = "";
            }
            else tmp += c;
        }
        filename = tmp; //最后一部分存文件名
    }
    pair<file*, int> find(){ //查找路径的属性 0-路径错误 1-路径不完整 2-成功找到
        file *now = root; //从根目录开始
        for(auto &np:path){ //遍历路径的每一个元素
            if(!now -> ch.count(np)) return make_pair(nullptr,1); //路径不存在
            if(now->ch[np]->file_type == 0) return make_pair(nullptr,0);  //路径错误
            now = now->ch[np];
        }
        if(!filename.empty()){ //如果不是根目录
            if(!now->ch.count(filename)) return make_pair(nullptr,1);
            now = now->ch[filename];
        }
        return make_pair(now,2);
    }
    bool create(ll size){  //创建一个文件
        file *now = root;
        for(auto &np:path){ //预分配判断是否合法
            if(!now->pre_add_size(size)) return false; //路径不合法
            if(!now->ch.count(np)) now->ch[np] = new file(1); //孩子目录不存在，新建目录文件
            now = now->ch[np];
        }
        if(!now->pre_add_size(size,true)) return false; //对最后一层路径进行检查
        //实际分配
        now = root;
        for(auto &np:path){
            now->add_size(size);
            now = now->ch[np];
        }
        now->add_size(size,true);
        now->ch[filename] = new file(0,size); //新建文件
        return true;
    }
    void remove(ll size){  //删除一个文件
        file *now = root;
        for(auto &np:path){
            now->add_size(-size);
            now = now->ch[np];
        }
        if(now->ch[filename]->file_type == 1)
            now->add_size(-size);//目录文件直接-size
        else
            now->add_size(-size,true); //删子树同时删孩子节点
        delete now->ch[filename];
        now->ch.erase(filename);
    }
}fs;


int main(){
    int n;
    scanf("%d",&n);
    string s, pa;
    for(int i = 0; i < n; i++){
        cin >> s >> pa;
        fs.set_path(pa);
        auto ret = fs.find();
        if(s == "C"){
            ll filesize;
            cin>>filesize;
            if(ret.second == 2){//路径完整
                if(ret.first ->file_type == 1) pn; //目录文件
                else{
                    ll old_size = ret.first->get_size();
                    fs.remove(old_size);
                    if(fs.create(filesize)) py;
                    else{
                        fs.create(old_size);
                        pn;
                    }
                }
            }
            else if(ret.second == 1){ //路径不完整
                if(fs.create(filesize)) py;
                else pn;
            }
            else pn;
        }
        else if(s == "R"){
            if(ret.second == 2)
                fs.remove(ret.first->get_size());
            py;
        }
        else if(s == "Q"){
            ll all_mx, son_mx;
            cin>>son_mx >> all_mx;
            if(ret.second == 2 && ret.first ->file_type == 1){
                if(ret.first->set_size(all_mx,son_mx)) py;
                else pn;
            }
            else pn;
        }
    }
    return 0;
}

H10

A : 小明上学

题目背景

小明是汉东省政法大学附属中学的一名学生，他每天都要骑自行车往返于家和学校。为了能尽可能充足地睡眠，他希望能够预计自己上学所需要的时间。他上学需要经过数段道路，相邻两段道路之间设有至多一盏红绿灯。

京州市的红绿灯是这样工作的：每盏红绿灯有红、黄、绿三盏灯和一个能够显示倒计时的显示牌。假设红绿灯被设定为红灯 rr 秒，黄灯 yy 秒，绿灯 gg 秒，那么从 00 时刻起，[0,r)[0,r) 秒内亮红灯，车辆不许通过；[r, r+g)[r,r+g) 秒内亮绿灯，车辆允许通过；[r+g, r+g+y)[r+g,r+g+y) 秒内亮黄灯，车辆不许通过，然后依次循环。倒计时的显示牌上显示的数字 l(l > 0)l(l>0)是指距离下一次信号灯变化的秒数。

问题描述

一次上学的路上，小明记录下了经过每段路的时间，和各个红绿灯在小明到达路口时的颜色和倒计时秒数。希望你帮忙计算此次小明上学所用的时间。

输入格式

输入的第一行包含空格分隔的三个正整数 rr、yy、gg，表示红绿灯的设置。这三个数均不超过 10^6106。

输入的第二行包含一个正整数 n(n \leq 100)n(n≤100)，表示小明总共经过的道路段数和看到的红绿灯数目。

接下来的 nn 行，每行包含空格分隔的两个整数 kk、tt。k=0k=0 表示经过了一段道路，耗时 tt 秒，此处 tt 不超过 10^6106；k=1k=1、22、33 时，分别表示看到了一个红灯、黄灯、绿灯，且倒计时显示牌上显示的数字是 tt，此处 tt 分别不会超过 rr、yy、gg。

输出格式

输出一个数字，表示此次小明上学所用的时间。

样例输入

30 3 30
8
0 10
1 5
0 11
2 2
0 6
0 3
3 10
0 3

样例输出

70

样例说明

小明先经过第一段道路，用时 1010 秒，然后等待 55 秒的红灯，再经过第二段道路，用时 1111 秒，然后等待 22 秒的黄灯和 3030 秒的红灯，再经过第三段、第四段道路，分别用时66、33秒，然后通过绿灯，再经过最后一段道路，用时 33 秒。共计 10 + 5 + 11 + 2 + 30 + 6 + 3 + 3=7010+5+11+2+30+6+3+3=70 秒。

评测用例规模与约定

测试点 1, 2 中不存在任何信号灯。 测试点 3, 4 中所有的信号灯在被观察时均为绿灯。 测试点 5, 6 中所有的信号灯在被观察时均为红灯。 测试点 7, 8 中所有的信号灯在被观察时均为黄灯。 测试点 9, 10 中将出现各种可能的情况。

代码：

#include<bits/stdc++.h>
using namespace std;

long long r, y, g;
int n;
int k;
long long t;
long long res = 0;

int main(){
    cin >> r >> y >> g;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> k;
        cin >> t;
        switch (k){
            case 0:{
                res += t;
                break;
            }
            case 1:{
                res += t;
                break;
            }
            case 2:{
                res += t;
                res += r;
            }
            case 3:
                break;
            default:
                break;
        }
    }
    cout << res << "\n";
    return 0;
}

B : 小中大

题目背景

在数据分析中，最小值最大值以及中位数是常用的统计信息。

题目描述

老师给了你 nn 个整数组成的测量数据，不保证有序，可能存在重复的数据。请统计出这组测量数据中的最大值、中位数以及最小值，并按照从大到小的顺序输出这三个数。

输入格式

从标准输入读入数据。 第一行输入一个整数 nn，在第二行中存在 nn 个整数，表示测量数据，可能存在多个整数相等，整数与整数之间使用空格隔开。

输出格式

输出到标准输出。 包含一行，包括最大值、中位数以及最小值共三个数，并按照从大到小的顺序输出。数据与数据之间使用空格隔开。对于整数请直接输出整数，对于可能出现的分数，请输出四舍五入保留 11 位小数的结果。

样例1输入

3
-1 2 4

样例1输出

4 2 -1

样例1解释

44 为最大值，22 为中位数，-1−1 为最小值。

样例2输入

4
-2 -1 3 4

样例2输出

4 1 -2

样例2解释

44 为最大值，(-1+3)÷2=1(−1+3)÷2=1 为中位数，-2−2为最小值。

子任务

代码：

#include<bits/stdc++.h>
using namespace std;

int n;
long long temp;
vector<long long> v;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(),v.begin() + n);
    cout << v[n-1] <<" ";
    if(n % 2 == 0){
        if ( (v[n/2-1] + v[n/2])%2 == 0)
            cout << (v[n/2-1] + v[n/2])/2 <<" ";
        else
            cout << fixed<< setprecision(1) << (v[n/2-1] + v[n/2])/2.0 <<" ";
    }
    else
        cout << v[n/2] <<" ";
    cout << v[0];
    return 0;
}
//4 6 10 11 14 17 18

C : 树状数组

题目描述

给定数列 a1,a2,…,an，你需要依次进行q个操作，操作有两类：

• 1 i x：给定 i,x，将 a_i加上 x；

• 2 l r：给定 l,r,求 ∑i=l,r ai的值（换言之，求 al+al+1+⋯+ar 的值）。

输入格式

第一行包含 22 个正整数 n,q，表示数列长度和询问个数。保证1≤n,q≤10^6。 第二行 n个整数a1​,a2​,…,an，表示初始数列。保证 |a_i|≤10^6。 接下来 q行，每行一个操作，为以下两种之一：

• 1 i x：给定 i,x，将 a[i] 加上 x；

• 2 l r：给定 l,r，求 ∑i=lrai 的值。

保证 1≤l≤r≤n, ∣x∣≤10^6。

输出格式

对于每个 2 l r 操作输出一行，每行有一个整数，表示所求的结果。

样例

输入样例

3 2
1 2 3
1 2 0
2 1 3

输出样例

6

数据范围

对于所有数据，1≤n,q≤10^6, |a_i|≤10^6, 1≤l≤r≤n, |x|≤10^6。

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxN 1000005
long long n, q;
long long s[maxN];
long long a[maxN];
long long flag, num1, num2;
long long lowbit(long long x){
    return x & (-x);
}
void upd(long long x, long long v){
    for(long long i = x; i <= n; i += lowbit(i))
        s[i] += v;
}
long long ask(long long x){
    long long res = 0;
    for(long long i = x; i >= 1; i -= lowbit(i))
        res += s[i];
    return res;
}

int main(){
    scanf("%ld%ld",&n,&q);
    for(int i = 0; i < maxN; i++){
        s[i] = 0;
    }
    long long temp;
    for(long long i = 1; i <= n; i++){
        scanf("%ld",&temp);
        upd(i,temp);
    }
    for(long long i = 0; i < q; i++){
        scanf("%ld%ld%ld",&flag,&num1,&num2);
    //    cin >> flag >> num1 >> num2;
        if(flag == 1)
            upd(num1,num2);
        else
            printf("%ld\n",ask(num2) - ask(num1 - 1));
    }
    return 0;
}

D : 排名

题目描述

sys 参加了一场 AI 算法大赛，大赛要求参赛者提供一个程序，后台的评测系统会使用相同的数据对所有提交程序进行评测，通过程序的运行时间与内存占用来衡量一个算法的好坏。

比赛的成绩计算方法为，给每一个程序进行打分，对于一个程序来说，该程序的得分为：运行时间与内存占用均小于等于该程序的程序的数量。

现在需要你来计算，成绩为 0,1,\dots n-10,1,…n−1 的程序的数量分别为多少。

输入格式

第一行一个整数 NN，表示程序的数目； 接下来 NN 行给出每个程序的运行时间与内存占用，用两个空格隔开的整数表示； 不会有两个程序的运行时间与内存占用均相同。

输出格式

nn 行，每行一个整数，分别是得分为 00，11，22，\dots…，n-1n−1 的程序的数目。

样例

输入

5
1 1
5 1
7 1
3 3
5 5

输出

1
2
1
1
0

数据范围

对于全部数据，1\le n\le 10^61≤n≤106，0\le 运行时间,内存占用 \le 10^60≤运行时间,内存占用≤106。

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxN 1000005
int tree[maxN] = {0};
int N;
int score[maxN] = {0};
int mx = 0;
struct program{
    int running_time;
    int memory_size;
//    program(int a, int b) {running_time = a; memory_size = b;}
};
vector<program> v;
bool cmp(program a, program b){
    if(a.running_time == b.running_time)
        return a.memory_size < b.memory_size;
    else
        return a.running_time < b.running_time;
}
int lowbit(int x){
    return x&(-x);
}
void upd(int x, int val){
    for(int i = x; i <= mx+1; i+= lowbit(i))
        tree[i] += val;
}
int sum(int x){
    int res = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
        res += tree[i];
    return res;
}
int main(){
    scanf("%d",&N);
    int a,b;
    for(int i = 1; i <= N; i++){
        scanf("%d%d",&a,&b);
        program temp;
        mx = max(mx,b);
        temp.running_time = a;
        temp.memory_size = b;
        v.push_back(temp);
    }
    sort(v.begin(),v.end(),cmp);
    for(int i = 0; i < N; i++){
    //    printf("%d\n",sum(v[i].memory_size));
        upd(v[i].memory_size+1,1);
        score[sum(v[i].memory_size+1)-1]++;
    }
    for(int i = 0; i < N; i ++){
        printf("%d\n",score[i]);
    }
    return 0;
}

E : 火星饭店

题目描述

lzh 在火星开了一家饭店，为了吸引顾客，饭店会不定期在菜谱中加入新菜，每个菜都有一个美味度 l(0\le l < p)l(0≤l<p)。

饭店使用手机进行点餐，手机上展示的菜谱会按照更新的顺序逆序排列。由于不同顾客的手机屏幕分辨率大小不同，所以能够显示在第一屏的菜谱的数量也不同。根据调查发现，火星用户只会在第一屏的菜品中选择美味度最高的购买。

现在按照时间顺序输入 mm 个添加菜品或顾客点菜的操作，请输出每位点菜顾客所点的菜的美味度。

输入格式

第一行有两个正整数 m,pm,p，意义如题目描述；

接下来 mm 行，每一行表示一个操作。

• 如果该行的内容是 Q L，则表示有顾客进行了点菜，该顾客的手机屏幕可以显示 LL 个菜品；

• 如果是A t，则表示加入了新的菜品，菜品的美味度是(t+a)\bmod p(t+a)modp。

  • tt 是输入的参数

  • aa 是在这个添加操作之前最后一个点菜操作的答案（如果之前没有点菜操作，则 a = 0a=0）。

数据保证第一个操作一定是添加菜品。在顾客点菜时，L\gt 0L>0 且不超过当前已有菜品的数量。

输出格式

对于每一个点菜操作，输出一行。该行只有一个数，即当前屏幕中美味度最大的菜品的美味度。

样例

输入

10 100
A 97
Q 1
Q 1
A 17
Q 2
A 63
Q 1
Q 1
Q 3
A 99

输出

97
97
97
60
60
97

数据范围

对于全部数据，1\le m\le 2\times 10^5,1\le p\le 2\times 10^9,0\le t\lt p1≤m≤2×105,1≤p≤2×109,0≤t<p。

代码：

#include<bits/stdc++.h>
using namespace std;

#define maxN 1000006
int mm; //行
long long pp;
char c;
int L;
long long t;
long long a[maxN], d[maxN << 1];
long long pre_a = 0;

void build(int x, int l, int r){
    if(l == r){
        d[x] = a[l];
        return;
    }
    int m = (l + r) / 2;
    build(x<<1, l, m);
    build(x<<1|1, m+1, r);
    d[x] = max(d[x<<1], d[x<<1|1]);
}
//int p,v;将p位置的值增加v
void upd(int p, long long v, int x, int l, int r){
    if(l == r){
        d[x] += v;
        return;
    }
    int m = (l + r) / 2;
    if(p <= m) upd(p, v, x<<1, l,m);
    else upd(p, v, x<<1|1,m+1,r);
    //由于孩子被更新，当前节点也要更新
    d[x] = max(d[x<<1], d[x<<1|1]);
}
//查询[p1,p2]的答案
long long ask(int x, int l, int r, int p1, int p2){
    //要查的区间刚好是当前区间，直接返回
    if(l == p1 && r == p2) return d[x];
    int m = (l + r) / 2;
    //情况1 要查询的区间完全在左边的区间
    if(p2 <= m) return ask(x<<1,l,m,p1,p2);
        //情况2 要查询的区间完全在右边的区间
    else if(p1 > m) return ask(x<<1|1,m+1,r,p1,p2);
        //情况3 要查询的区间分布在左右两边，分别计算，合并后作为答案
    else
        return max(ask(x<<1,l,m,p1,m),ask(x<<1|1,m+1,r,m+1,p2));
}
int main(){
    scanf("%d%lld",&mm,&pp);
    for(int i = 1; i <= mm; i++){
        a[i] = 0;
    }
    int num = 0; //记录位置
//    build(1,1,n);
    for(int i = 0; i < mm; i++){
        cin >> c;
        if(c == 'A'){
            scanf("%lld",&t);
            t = (t + pre_a) % pp;
            num++;
            upd(num,t,1,1,mm);
        }
        if(c == 'Q'){
            scanf("%d",&L);
            int rr = num;
            int ll = max(num - L + 1,1);
            pre_a = ask(1,1,mm,ll,rr);
            printf("%lld\n",pre_a);
        }
    }
    //   system("pause");
    return 0;
}

H11

A : 爬台阶

题目描述

楼上有 nn 级台阶，其中有 mm 级台阶是不安全的。yhf一开始站在第 00 级台阶上，希望最终走到第 nn 级台阶

yhf跨一步满足以下约束：

• 只能向前走

• 不能落脚在不安全的台阶上

• 最多迈 kk 级台阶

• 落脚点不能超过第 nn 级台阶

也就是说，若某一刻yhf站在第 cc 级台阶上，那么他下一步可以落脚的位置 xx 满足 c < x \le min(c + k, n)c<x≤min(c+k,n) 且第 xx 级台阶是安全的。那么，yhf有多少种方法走到第 nn 级台阶

输入格式

第一行三个整数 n, m, kn,m,k ，描述见上文

第二行 mm 个整数，d_1, d_2 ,...,d_md1,d2,...,d**m ，其中 1 \le d_i < n1≤d**i<n ，表示不安全台阶的编号

输出格式

一个整数，模 998244353998244353 后的方案数

测试样例

样例输入

5 1 2
3

样例输出

2

数据规模

对于 100 \%100% 的数据，1 \le m < n \le 10^6, 1 \le k \le 10^61≤m<n≤106,1≤k≤106

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxN 1000005
int n,m,k; //一共n级台阶，其中m级台阶不安全，最多迈k级台阶
long long sf[maxN] = {0}; //前缀和 1-n
long long f[maxN] ={0}; //到每一级方案数
int main(){
    scanf("%d%d%d",&n,&m,&k);
    int temp;
    for(int i = 0; i < m; i++){
        scanf("%d",&temp); //不安全的台阶
        f[temp] = -1; //标记
    }
    f[0] = 1;
    sf[0] = 1;
    int ll;
    bool flag = 1;
    for(int i = 1; i <= n; i++){
        if(flag && f[i] != -1) {
            f[i] = 1;
            sf[i] = sf[0] + f[i];
            for(int j = i-1; j > 0; j--)
                sf[j] = 1;
            flag = 0;
            continue;
        }
        if(f[i] != -1){
            if(i-k-1 < 0)
                f[i] = sf[i-1];
            else{
                f[i] = (sf[i-1] - sf[i-k-1])%998244353;
                if(f[i] < 0) f[i] += 998244353;
            }
        }
        else
            f[i] = 0; //不安全的台阶
        sf[i] = (sf[i-1] + f[i])%998244353;
        if(sf[i] < 0)
            sf[i] += 998244353;
    }
    printf("%ld\n",f[n]);
    return 0;
}

B : 拿数问题

题目描述

给定 nn 个数，我们要从中选出多若干个数，其中任意大小不同的两数差的绝对值不能为 11，那么选出的数之和最大是多少。

输入格式

第一行一个整数 nn 。

第二行 nn 个整数，a_1,a_2 ,...,a_na1,a2,...,a**n ，表示这 nn 个数

输出格式

一个整数，选出的数的和的最大值

测试样例

样例输入

5
1 1 3 2 3

样例输出

8

数据规模

对于 100 \%100% 的数据，1 \le n \le 10^6, 1 \le a_i \le 10^61≤n≤106,1≤a**i≤106

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxN 1000005
long long cnt[maxN] = {0};
long long dp[maxN] = {0};
int n;
long long maxnum;

int main(){
    cin >> n;
    long long temp;
    for(int i = 0; i < n; i++){
        scanf("%ld",&temp);
        cnt[temp] ++;
        maxnum = max(maxnum, temp);
    }
    dp[1] = cnt[1];
    for(long long i = 2; i <= maxnum; i++){
        dp[i] = max(dp[i-1],dp[i-2] + cnt[i] * i);
    }
    printf("%ld",dp[maxnum]);
    return 0;
}

C : 矩阵选数

题目描述

给定一个 33 行，nn 列的矩阵，我们要在矩阵的每一列选一个数。对于第 i(1 \le i \le n)i(1≤i≤n) 列，我们令 d_id**i 为第 ii 列选择的数。那么，\sum_1^{n-1}|d_i - d_{i+1}|∑1n−1∣d**i−d**i+1∣ 最小是多少

输入格式

第一行一个整数 nn ，描述见上文

后面三行每行 nn 个整数，为矩阵的各个元素

输出格式

一个整数，题目要求的最小值

测试样例

样例输入

5
5 10 5 4 4
1 7 8 4 0
3 4 9 0 3

样例输出

3

数据规模

对于 100 \%100% 的数据，1 \le n \le 10^61≤n≤106 ，矩阵中数据绝对值不超过 10^6106

#include<bits/stdc++.h>
using namespace std;
#define maxN 1000005
long long dp[3][maxN];
int n;
long long a[3][maxN];
int main(){
    scanf("%d",&n);
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < n; j++){
            scanf("%ld",&a[i][j]);
            dp[i][j] = LONG_MAX;
        }
    }
    dp[0][0] = 0; dp[1][0] = 0; dp[2][0] = 0;
    for(int i = 1; i < n; i++){
        dp[0][i] = min(dp[0][i-1] + abs(a[0][i] - a[0][i-1]),
                       dp[1][i-1] + abs(a[0][i] - a[1][i-1]));
        dp[0][i] = min(dp[0][i],dp[2][i-1] + abs(a[0][i] - a[2][i-1]));
        dp[1][i] = min(dp[0][i-1] + abs(a[1][i] - a[0][i-1]),
                       dp[1][i-1] + abs(a[1][i] - a[1][i-1]));
        dp[1][i] = min(dp[1][i],dp[2][i-1] + abs(a[1][i] - a[2][i-1]));
        dp[2][i] = min(dp[0][i-1] + abs(a[2][i] - a[0][i-1]),
                       dp[1][i-1] + abs(a[2][i] - a[1][i-1]));
        dp[2][i] = min(dp[2][i],dp[2][i-1] + abs(a[2][i] - a[2][i-1]));

    }
    long long ans = dp[0][n-1];
    for(int j = 1; j < 3; j++){
        ans = min(ans, dp[j][n-1]);
    }
    printf("%ld",ans);
    return 0;
}

D : 最长上升子序列

题目描述

对于一个整数序列 A =(a_1, a_2,\ldots , a_k)A=(a1,a2,…,a**k)，定义 AA 的子序列为：从 AA 中删除若干个元素后（允许不删，也允许将所有 kk 个元素都删除），剩下的元素按照原来的顺序所组成的序列。如果这个子序列的元素从左到右严格递增，则称它为 AA 的一个上升子序列。其中包含元素数量最多的上升子序列称为 AA 的最长上升子序列。例如，(2, 4, 5, 6)(2,4,5,6) 和 (1, 4, 5, 6)(1,4,5,6) 都是 (2, 1, 1, 4, 7, 5, 6)(2,1,1,4,7,5,6) 的最长上升子序列，长度都为 44。

那么，给定一个序列 A =(a_1, a_2,\ldots , a_n)A=(a1,a2,…,a**n)， 求 AA 的最长上升子序列的长度

输入格式

第一行一个整数 nn ，代表序列 AA 的长度

第二行是 nn 个由空格隔开的整数，代表 a_1, a_2,\ldots , a_na1,a2,…,a**n

输出格式

一个整数，代表最长上升子序列的长度

测试样例

样例输入

7
2 1 1 4 7 5 6

样例输出

4

数据规模

对于 $100% $ 的数据，1 \le n \le 10^6, 1\le a_i \le10^61≤n≤106,1≤a**i≤106

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxN 1000005
int n;
int a[maxN] = {0},dp[maxN] = {0};
int s[maxN] = {0}; //树状数组
int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
        a[i] ++;
    }
    for(int i = 1; i <= n; i++){
        int res = 0;
        for(int x = a[i] - 1; x >= 1; x -= (x & (-x)))
            res = max(res,s[x]);
        dp[i] = res + 1;
        for(int x = a[i]; x <= maxN; x += (x & (-x)))
            s[x] = max(s[x],dp[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans,dp[i]);
    }
    printf("%d",ans);
    return 0;
}

E : 最长公共子序列

题目描述

给定序列 A =(a_1, a_2,\ldots , a_n)A=(a1,a2,…,a**n) 和 B =(b_1, b_2,\ldots , b_m)B=(b1,b2,…,b**m) ，求它们的最长公共子序列

子序列的定义参考题目 最长上升子序列

输入格式

第一行两个整数 n, mn,m 代表序列 A,BA,B 的长度

第二行是 nn 个由空格隔开的整数，代表 a_1, a_2,\ldots , a_na1,a2,…,a**n

第三行是 mm 个由空格隔开的整数，代表 b_1,b_2,\ldots , b_mb1,b2,…,b**m

输出格式

输出一个整数，代表最长公共子序列的长度

测试样例

样例输入

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

样例输出

3

数据规模

对于 100 \%100% 的数据，1 \le n, m \le 5000, 1\le a_i, b_i\le10^41≤n,m≤5000,1≤a**i,b**i≤104

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxN 5005
int n,m;
int a[maxN];
int b[maxN];
int f[maxN][maxN];
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)
        scanf("%d",&a[i]);
    for(int i = 1; i <= m; i++)
        scanf("%d",&b[i]);
    f[1][0]=f[0][1]=f[0][0] = 0;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j++){
            if(a[i] == b[j])
                f[i][j] = f[i-1][j-1] + 1;
            else
                f[i][j] = max(f[i-1][j],f[i][j-1]);
        }
    }
    printf("%d",f[n][m]);
    return 0;
}

H12:

A : 01背包

题目描述

有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述

第一行为N(1≤N≤5000)(1≤N≤5000)，V(1≤V≤5000)(1≤V≤5000)。

下面N行，第i行描述第i个物品的wi(1≤w[i]≤103)，ci(1≤c[i]≤103)，用一个空格分隔。

输出描述

输出只有一个数，最大总价值。

Input

10 9
7 1
8 10
7 10
7 7
7 6
3 7
4 1
3 3
9 1
1 4

Output

14

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxN 5005
int N,V;
int w[maxN],c[maxN];
int f[maxN][maxN];
int main(){
    scanf("%d%d",&N,&V);
    for(int i = 1; i <= N; i++){
        scanf("%d%d",&w[i],&c[i]);
    }
    for(int i = 1; i <= N; i++)
        for(int j = 0; j <= V; j++){
           f[i][j] = f[i-1][j];
            if(j - w[i] >=0)
                f[i][j] = max(f[i][j],f[i-1][j-w[i]]+c[i]);
        }
    printf("%d",f[N][V]);
    return 0;
}

B : 完全背包

题目描述

有N种物品（每种有无限多个）和一个容量为V的背包。第i种物品的重量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述

第一行为N(1≤N≤5000)(1≤N≤5000)，V(1≤V≤5000)(1≤V≤5000)。

下面N行，第i行描述第i种物品的wi(1≤w[i]≤103)，ci(1≤c[i]≤103)，用一个空格分隔。

输出描述

输出只有一个数，最大总价值。

Input

10 8
4 5
1 1
1 5
5 4
5 10
6 5
1 1
5 6
7 4
4 5

Output

40

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxN 5005
int N,V;
int w[maxN],c[maxN];
int f[maxN];
int main(){
    scanf("%d%d",&N,&V);
    for(int i = 1; i <= N; i++)
        scanf("%d%d",&w[i],&c[i]);
    for(int i = 1; i <=N; i++)
        for(int j = w[i]; j <= V; ++j)
            f[j] = max(f[j],f[j - w[i]] + c[i]);
    printf("%d",f[V]);
    return 0;
}

C : 多重背包

题目描述

有N种物品和一个容量为V的背包。第i种物品的重量是w[i]，价值是c[i]，有k[i]个。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述

第一行为N(1≤N≤10^4)(1≤N≤104)，V(1≤V≤10^4)(1≤V≤104)。

下面N行，第i行描述第i种物品的wi(1≤w[i]≤102)，ci(1≤c[i]≤106)，ki(1≤k[i]≤102)，用一个空格分隔。

输出描述

输出只有一个数，最大总价值。

Input

6 1
7 10 4
6 9 1
6 8 1
10 6 2
9 8 3
1 3 2

Output

3

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxN 10005
int N,V;
int w[maxN],k[maxN],ww[maxN * 100];
long long f[maxN];
long long c[maxN],cc[maxN * 100];

int main(){
    scanf("%d%d",&N,&V);
    for(int i = 1; i <= N; i++)
        scanf("%d%lld%d",&w[i],&c[i],&k[i]);
    int cnt =0;
    for(int i = 1; i <= N; i++){
        int t = k[i];
        for(int j = 1; j <= t; j <<=1){
            cnt++;
            cc[cnt] = (long long)j * c[i];
            ww[cnt] = j * w[i];
            t -= j;
        }
        if(t > 0){
            cnt ++;
            cc[cnt] = (long long)t * c[i];
            ww[cnt] = t * w[i];
        }
    }
    for(int i = 1; i <= cnt; i++)
        for(int j = V; j >= ww[i]; --j)
            f[j] = max(f[j],f[j-ww[i]] + cc[i]);
    printf("%lld",f[V]);
    return 0;
}

D : 分组背包

题目描述

有N件物品和一个容量为V的背包，将所有的物品划分成若干组，每个组里面的物品最多选一件。第i件物品的重量是w[i]，价值是c[i]，属于组k[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述

第一行为N(1≤N≤10^3)(1≤N≤103)，V(1≤V≤10^3)(1≤V≤103)。

下面N行，第i行描述第i个物品的wi(1≤w[i]≤102)，ci(1≤c[i]≤106)，ki(1≤k[i]≤102)，用一个空格分隔。

输出描述

输出只有一个数，最大总价值。

Input

7 9
6 6 3
5 10 3
3 5 1
9 4 4
6 1 4
8 3 5
5 2 2

Output

15

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxN 1005
int N,V;
long long dp[maxN];
vector<pair<int,long long> > vvv[103];
int main(){
    scanf("%d%d",&N,&V);
    int x;
    long long y;
    int z;
    int ts = 0; //记录组数
    for(int i = 0; i < 103; i++)
        vvv[i].emplace_back(0,0);
    for(int i = 1; i <= N; i++){
        scanf("%d%lld%d",&x,&y,&z);
        vvv[z].emplace_back(x,y);
        ts = max(z,ts);
    }
    for(int k = 1; k <= ts; k++){
        for(int i = V; i >= 0; i--)
            for(int j = 1; j < vvv[k].size(); j++)
                if(i >= vvv[k][j].first)
                    dp[i] = max(dp[i],dp[i-vvv[k][j].first] + vvv[k][j].second);

    }
    printf("%lld",dp[V]);
    return 0;
}

E : 超大背包

题目描述

有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述

第一行为N(1≤N≤40)(1≤N≤40)，V(1≤V≤10^{15})(1≤V≤1015)。

下面N行，第i行描述第i个物品的wi(1≤w[i]≤1015)，ci(1≤c[i]≤1015)，用一个空格分隔。

输出描述

输出只有一个数，最大总价值。

Input

3 225274242
70498827 830583485
72910089 759360759
80945586 1095298545

Output

2685242789

代码：

#include<bits/stdc++.h>
using namespace std;

vector<pair<long,long> > vvv[2];
long long w[50],v[50];
long long N;
long long V;
vector<pair<long long, long long> > vv1,vv2; // w,v
int main(){
    scanf("%lld%lld",&N,&V);
    for(long long i = 0; i < N; i ++)
        scanf("%lld%lld",&w[i],&v[i]);
    long long n1 = N/2;
    long long n2 = N/2 + 1;
    long long num1 = 1 << n1;
    for(long long i = 0 ; i < num1; i++){
        long long tempw = 0, tempv = 0;
        for(long long j = 0; j < n1; j++){
            tempw += ((i >> j)&1) * w[j];
            tempv += ((i >> j)&1) * v[j];
        }
        vv1.emplace_back(tempw,tempv);
    }
    long long num2 = 1 << (N-n1);
    for(long long i = 0; i < num2; i++){
        long long tempw = 0, tempv = 0;
        for(long long j = 0; j < N-n1; j++){
            tempw += ((i >> j)&1) * w[j+n1];
            tempv += ((i >> j)&1) * v[j+n1];
        }
        vv2.emplace_back(tempw,tempv);
    }
    sort(vv1.begin(),vv1.begin()+num1);
    vector<pair<long long, long long> > v1;
    v1.push_back(vv1[0]);
    for(long long i = 0; i < num1; i++)
        if(v1.back().second < vv1[i].second)
            v1.push_back(vv1[i]);
    long long res = 0;
    for(long long i = 0; i < vv2.size(); i++){
        if(vv2[i].first <= V){
            long long x = V-vv2[i].first;
            long long y = (upper_bound(v1.begin(), v1.end(),make_pair(x, LONG_LONG_MIN))-1)->second;
            //long long y = (*it).second;
            res = max(res,y + vv2[i].second);
        }
    }
    printf("%lld",res);
    return 0;
}

H13:

A : 石子合并

题目描述

将 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数N及每堆的石子数，并进行如下计算：

1. 选择一种合并石子的方案，使得做 次合并得分总和最大。

2. 选择一种合并石子的方案，使得做 次合并得分总和最小。

输入描述

输入第一行一个整数N(1≤N≤100)(1≤N≤100)，表示有N堆石子。

第二行N个整数，表示每堆石子的数量。

输出描述

输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

Input

4
4 5 9 4

Output

43
54

代码：

#include<bits/stdc++.h>
using namespace std;
const long long inf = INT_MAX;
int N;
long long w[205];
long long f[205][205];
long long F[205][205];
long long sum[205];

int main(){
    for(int i = 0; i < 205; i++)
        for(int j = 0; j < 205; j++){
            f[i][j] = inf;
            F[i][j] = 0;
        }
    for(int i = 0; i < 205; i++){
        f[i][i] = 0;
    }
    scanf("%d",&N);
    for(int i = 1; i <= N; i++){
        scanf("%lld",&w[i]);
        w[i+N] = w[i];
    }

    for(int i = 1; i <= 2*N; i++)
        sum[i] = sum[i-1] + w[i];
    for(int len = 2; len <= 2*N; len++){
        for(int i = 1; i <= 2*N - len + 1; i++){
            int l = i,r = i+len-1;
            for(int k = l; k < r; ++k){
                f[l][r]= min(f[l][r], sum[r]-sum[l-1] + f[l][k] + f[k+1][r]);
                F[l][r] = max(F[l][r],sum[r]-sum[l-1] + F[l][k] + F[k+1][r]);
            }
        }
    }
    long long minnum = inf;
    long long maxnum = 0;
    for(int i = 1; i <= N; i++){
        minnum = min(minnum,f[i][i + N - 1]);
        maxnum = max(maxnum,F[i][i+N-1]);
    }
    printf("%lld\n",minnum);
    printf("%lld\n",maxnum);
    return 0;
}

B : 括号序列

题目描述

定义一个合法的括号序列

• 空序列合法

• 如果S合法，那么(S)和[S]合法

• 假设A和B合法，那么AB合法

合法序列 - ()，[]，(())，([])，()[]，()[()]

非法序列 - (，[，]，)(， (])，([()，([)]

给定一个序列，求最少添加多少个括号，才能得到一个合法序列。

输入描述

输入仅一行，为一个字符串S

输出描述

输出只有一个整数，表示增加的最少字符数。

Input

[])

Output

1

代码：

#include<bits/stdc++.h>
#define maxN 200
using namespace std;
string s;
int num;
int dp[maxN][maxN];
int main(){
    cin >> s;
    int length = (int)s.size();
    s = " "+ s;
    for(int i = 0; i < maxN; i++)
        for(int j = 0; j < maxN; j++)
            dp[i][j] = INT_MAX / 2;
    for(int i = 0; i < maxN; i++)
        dp[i][i] = 1;
    for(int i = 1; i <= length-1; i++) {
        if ((s[i] == '(' && s[i + 1] == ')') || (s[i] == '[') && (s[i + 1] == ']'))
            dp[i][i + 1] = 0;
        else
            dp[i][i - 1] = 2;
    }
    for(int len = 2; len <= length; len++){
        for(int i = 1; i <= length - len + 1; i++){
            int l = i;
            int r = l + len - 1;
            if((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']'))
                dp[l][r] = min(dp[l][r],dp[l+1][r-1]);
            if(s[l] == '(' || s[l] == '[')
                dp[l][r] = min(dp[l][r],dp[l+1][r] + 1);
            if(s[r] == ')' && s[l] == ']')
                dp[l][r] = min(dp[l][r],dp[l][r-1] + 1);
            for(int k = l; k <= r; k++)
                dp[l][r] = min(dp[l][k] + dp[k+1][r],dp[l][r]);
        }
    }
    printf("%d\n",dp[1][length]);
}

C : 最长回文子序列

题目描述

给定一个字符串S ，找到其中最长的回文子序列，并返回该序列的长度。

输入描述

输入为一个只包含小写英文字母的字符串S，最大长度不超过3000。

输出描述

输出最长回文子序列的长度。

Input

abcb

Output

3

代码：

#include<bits/stdc++.h>
#define maxN 4005
using namespace std;
string s;
int dp[maxN][maxN];
int main(){
    cin >> s;
    int length = s.size();
    s = " " + s;
    for(int i = 0; i < maxN; i++)
        for(int j = 0; j < maxN; j++)
            dp[i][j] = 0;
    for(int i = 0; i < maxN; i++)
        dp[i][i] = 1;
    for(int len = 2; len <= length; len++){
        for(int i = 1; i <= length; i++){
            int l = i;
            int r = l + len - 1;
            if(s[l] == s[r])
                dp[l][r] = dp[l+1][r-1] + 2;
            else
                dp[l][r] = max(dp[l+1][r], dp[l][r-1]);
        }
    }
    printf("%d\n",dp[1][length]);
    return 0;
}

D : 方格填充

题目描述

将高为H，宽为W的棋盘分割成若干个宽和高分别为1和2的长方形，有多少种方案。

输入描述

第一行为H(1≤N≤11)(1≤N≤11)，W(1≤W≤11)(1≤W≤11)。

输出描述

Input

2 2

Output

2

代码：

#include<bits/stdc++.h>
using namespace std;
int H,W;
long long f[12][1<<12];
bool fun(int s3){
    int x[12] = {0};
    for(int i = 0; i <W;i++){
        x[i] = s3&1;
        s3 = s3 >> 1;
    }
    int num = 0;
    for(int i = 0; i < W; i++){
        if(x[i] == 0)
            num ++;
        else{
            if(num % 2 == 1)
                return false;
            else
                num = 0;
        }
    }
    if(num & 1)
        return false;
    return true;
}
int main(){
    scanf("%d%d",&H,&W);
    for(int i = 0; i <= (1<<W)-1; i++)
        if(fun(i))
            f[1][i] = 1;
    for(int i = 2; i <= H; i++){
        for(int s1 = 0; s1 <= (1<<W)-1; s1++){
            for(int s2 = 0; s2 <= (1<<W)-1; s2 ++){
                if(((s1 & s2) == 0) && fun(s1|s2))
                    f[i][s1] += f[i-1][s2];
            }
        }
    }
    printf("%lld\n",f[H][0]);
    return 0;
}

H14:

A : 直径数量问题

题目描述

给出一棵树，求树的直径及其数量（最长简单路径的长度和数量）。

输入格式

第一行一个整数 nn , 0\le n\le10^50≤n≤105， 接下来有 n-1n−1 行，每行 a,ba,b 代表 aa 到第 bb 有一条长度为 11 的边。 1\le a,b\le n1≤a,b≤n

输出格式

输出两个数，分别表示树的直径和数量。

样例输入

5
5 1
1 2
2 3
2 4

样例输出

3 2

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxN = 100005;
int fa[maxN];
int deep[maxN],dp[maxN];
int res,num;
vector<int> Graph1[maxN];
int n;
int a,b;
void dfs(int i,int fa){
    bool isleaf = true;
    dp[i] = 1;
    for(int j = 0; j < (int)Graph1[i].size(); j++){
        if(Graph1[i][j] != fa) {
            isleaf = false;
            dfs(Graph1[i][j], i);
            if (deep[i] + deep[Graph1[i][j]] + 1 > res) {
                res = deep[i] + deep[Graph1[i][j]] + 1;
                num = dp[i] * dp[Graph1[i][j]];
            } else if (deep[i] + deep[Graph1[i][j]] + 1 == res)
                num += dp[i] * dp[Graph1[i][j]];
            if (deep[Graph1[i][j]] + 1 > deep[i]) {
                deep[i] = deep[Graph1[i][j]] + 1;
                dp[i] = dp[Graph1[i][j]];
            } else if (deep[Graph1[i][j]] + 1 == deep[i])
                dp[i] += dp[Graph1[i][j]];
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n-1; i++){
        scanf("%d%d",&a,&b);
        Graph1[a].push_back(b);
        Graph1[b].push_back(a);
    }
    dfs(1,-1); //以1号节点为根的树
    printf("%d %d\n",res,num);
    return 0;
}

B : 城市规划

题目描述

有一座城市，城市中有 NN 个公交站，公交站之间通过 N-1N−1 条道路连接，每条道路有相应的长度。保证所有公交站两两之间能够通过唯一的通路互相达到。 两个公交站之间路径长度定义为两个公交站之间路径上所有边的边权和。 现在要对城市进行规划，将其中 MM 个公交站定为“重要的”。 现在想从中选出 KK 个节点，使得这 KK 个公交站两两之间路径长度总和最小。输出路径长度总和即可（节点编号从 11 开始）。

输入格式

第 11 行包含三个正整数 N, MN,M 和 KK 分别表示树的节点数，重要的节点数，需要选出的节点数。 第 22 行包含 MM 个正整数，表示 MM 个重要的节点的节点编号。 接下来 N-1N−1 行，每行包含三个正整数 a, b, ca,b,c，表示编号为 aa 的节点与编号为 bb 的节点之间有一条权值为 cc 的无向边。每行中相邻两个数之间用一个空格分隔。

输出格式

输出只有一行，包含一个整数表示路径长度总和的最小值。

样例输入

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

样例输出

4

样例解释

样例中的树如上图所示。 重要的节点标号为 1, 3, 5，从中选出两个点，有三种方案: 方案 1: 1, 3 之间路径长度为 5 方案 2: 1, 5 之间路径长度为 4 方案 3: 3, 5 之间路径长度为 9

数据规模与子任务

数据点	NN	MM	KK
1, 21,2	\le 2000≤2000	\le 2000≤2000	\le 2≤2
3, 43,4	\le 5\times 10^4≤5×104	\le 16≤16	\le 16≤16
5, 6, 75,6,7	\le 2000≤2000	\le 2000≤2000	\le 100≤100
8, 9, 108,9,10	\le 5\times 10^4≤5×104	\le 10^4≤104	\le 100≤100

对于所有的数据，1≤a,b≤N，c≤10^5，M≤N，K≤M1≤a,b≤N，c≤105，M≤N，K≤M

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxN = 50009;
int N,M,K;
int a,b,c;
int flag[maxN] = {0}; //标记重要节点
int fa[maxN] = {0};
int num[maxN];
long long dp[maxN][109];
struct Edge {int v;int weight;};
vector<Edge> Graph[maxN];

void dfs(int x,int y){
    for(int i = 0; i < (int)Graph[x].size(); i++){
        if(Graph[x][i].v != y){
            fa[Graph[x][i].v] = x;
            dfs(Graph[x][i].v,x);
        }
    }
}

void dfs1(int i){
    if(flag[i]){
        num[i] += 2;
        dp[i][1] = 0;
    }
    for(int j = 0; j < Graph[i].size(); j++){
        if(Graph[i][j].v == fa[i]) continue;
        dfs1(Graph[i][j].v);
        num[i] += num[Graph[i][j].v];
        for(int s = min(num[i],K); s >= 0; s --){
            for(int l = 0; l <= s && l <= min(K,num[Graph[i][j].v]); l++){
                if(dp[Graph[i][j].v][l] != LONG_LONG_MAX && dp[i][s-l] != LONG_LONG_MAX)
                    dp[i][s] = min(dp[i][s],dp[Graph[i][j].v][l] + dp[i][s-l] + (long long)l * (K-l) * Graph[i][j].weight);
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    int tempnode;
    for(int i = 0; i < M; i++){
        scanf("%d",&tempnode);
        flag[tempnode] = 1;
    }
    for(int i = 1; i <= N-1; i++){
        scanf("%d%d%d",&a,&b,&c);
        Graph[a].push_back({b,c});
        Graph[b].push_back({a,c});
    }
    dfs(1,0);
    for(int i = 0; i < maxN; i++)
        for(int j = 0; j < 109; j++){
            dp[i][j] = LONG_LONG_MAX;
            dp[i][0] = 0;
        }
    dfs1(1);
    printf("%lld",dp[1][K]);
    return 0;
}

C : 最大区间和

题目描述

输入一个长度为 nn 的整数序列 aa，从中找出一段不超过 mm 的连续子序列（区间），使得这个序列的和最大。选出的区间可以为空。 n\le 10^6, m\le n, -10^9\le a_i\le 10^9n≤106,m≤n,−109≤a**i​≤109

输入描述

第一行两个数 n,mn,m，第二行 nn 个整数 a_ia**i 表示这个数列。

输出描述

一个整数表示答案。

样例输入

6 3
1 -3 5 1 -2 3

样例输出

6

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxN = 1000009;
int n,m;
long long a[maxN];
long long sum[maxN];
deque<long long> q;
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)
        scanf("%lld",&a[i]);
    long long ans = 0;
    for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i];
    q.push_back(0);
    for(int i = 1; i <= n; i++){
        while(!q.empty() && sum[q.back()] > sum[i])
            q.pop_back();
        q.push_back(i);
        while(!q.empty() && i - m > q.front())
            q.pop_front();
        ans = max(ans,sum[i] - sum[q.front()]);
    }
    printf("%lld",ans);
    return 0;
}

D : 帝国大厦

题目描述

帝国大厦共有 nn 层，LZH 初始时在第 aa 层上。 帝国大厦有一个秘密实验室，在第 bb 层，这个实验室非常特别，对 LZH 具有约束作用，即若 LZH 当前处于 xx 层，当他下一步想到达 yy 层时，必须满足 |x-y|<|x-b|∣x−y∣<∣x−b∣，而且由于实验室是不对外开放的，电梯无法停留在第 bb 层。 LZH 想做一次旅行，即他想按 kk 次电梯，他想知道不同的旅行方案个数有多少个。 两个旅行方案不同当前仅当存在某一次按下电梯后停留的楼层不同。

输入格式

一行 44 个数 n,a,b,kn,a,b,k。

输出格式

一个数表示答案，由于答案较大，将答案对 10^9+7109+7 取模后输出。

数据范围与子任务

对于 40\%40% 的数据 n,k\le 500n,k≤500。 对于 80\%80% 的数据 n,k\le 2000n,k≤2000。 对于 100\%100% 的数据 n,k\le 5000, 1 \le a,b \le n, a\neq bn,k≤5000,1≤a,b≤n,a\​=b。

Input

5 2 4 1

Output

2

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxN = 5009;
int n,a,b,k;
long long ans;
long long dp[maxN];
long long sum[maxN];
const long long m = 1e9 + 7;
int main(){
    scanf("%d%d%d%d",&n,&a,&b,&k);
    dp[a]  = 1;
    for(int i = a; i <= n; i++)
        sum[i] = 1;
    for(int i = 0; i < k; i++){
        for(int j = 1; j <= n; j++){
            if(j > b) {
                dp[j] = sum[n] - sum[(j+b)>>1] - sum[j] + sum[j-1];
                if(dp[j] > m)  dp[j] %= m;
                if(dp[j] < 0)  dp[j] = m + dp[j];
            }
            if(j < b){
                dp[j] = sum[(j+b-1) >> 1] - sum[j] + sum[j-1];
                if(dp[j] > m)  dp[j] %= m;
                if(dp[j] < 0)  dp[j] = m + dp[j];
            }
        }
        for (int j = 1; j <= n; j++)
            sum[j] = (sum[j-1] + dp[j]) % m;
    }
    for(int i = 1; i <= n; i++)
        ans = (ans + dp[i]) % m;
    printf("%lld",ans);
    return 0;
}

H15:

A : 斐波那契数列

题目描述

斐波那契数列的定义如下： 给出 n,pn,p ，求出 f(n)\%pf(n)%p 的值。

输入格式

第一行一个数 T(1\le T\le 100)T(1≤T≤100)，表示数据组数。 接下来 T 行，每行两个整数 n,p(1\le n\le 10^9,10^8\le p\le 10^9)n,p(1≤n≤109,108≤p≤109)。

输出格式

输出 T行，表示每组数据的答案。

Input

6
1 998244353
2 998244353
3 998244353
4 998244353
5 998244353
1000000000  998244353

Output

1
1
2
3
5
990450892

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2;
int n;
long long p;
int T;
struct Matrix{
    long long x[N][N];
    Matrix operator * (const Matrix& t) const{
        Matrix ret;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                ret.x[i][j] = 0;
                for(int k = 0; k < N; k++){
                    ret.x[i][j] += x[i][k] * t.x[k][j] % p;
                    ret.x[i][j] %= p;
                }
            }
        }
        return ret;
    }
    Matrix(){memset(x,0,sizeof x);}
    Matrix(const Matrix& t){memcpy(x,t.x,sizeof x);}
};
Matrix quick_pow(Matrix a,int x){
    Matrix ret;
    ret.x[0][1] = ret.x[1][0] = 0;
    ret.x[0][0] = ret.x[1][1] = 1;
    while(x) {
        if(x&1) ret = ret * a;
        a = a * a;
        x >>= 1;
    }
    return ret;
}
long long f(){
    if (n == 1 || n == 2) return 1;
    Matrix m1,m2;
    m1.x[0][0] = m1.x[0][1] = m1.x[1][0] = 1;
    m1.x[1][1] = 0;
    m2 = quick_pow(m1,n-2);
    return (m2.x[0][0] + m2.x[0][1])%p;
}
int main(){
    scanf("%d",&T);
    for(int i = 0; i < T; i++){
        scanf("%d%lld",&n,&p);
        printf("%lld\n",f());
    }
    return 0;
}

B : 自然数幂和

题目描述

给定 𝑛 和 𝑘，计算 \Sigma^{n}_{i=1}i^kΣi=1nik 对 10^9+7109+7 取模的结果。

输入格式

第一行一个数 T(1\le T\le 100)T(1≤T≤100)，表示数据组数。 接下来 T行，每行两个整数 n,k(1\le n\le 10^9,1\le k\le 10)n,k(1≤n≤109,1≤k≤10)。

输出格式

输出 T行，表示每组数据的答案。

Input

6
1 10
2 2
2 3
3 2
3 3
1000000000 9

Output

1
5
9
14
36
12313161

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 20
     int n,k;
ll mod=1e9+7;
struct matrix{
ll x[N][N];
matrix operator*(const matrix &t){
  matrix ret;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      ret.x[i][j]=0;
      for(int k=0;k<N;k++){
        ret.x[i][j]+=x[i][k]*t.x[k][j]%mod;
        ret.x[i][j]%=mod;
      }
    }
  }
return ret;
}
matrix(){memset(x,0,sizeof x);}
// matrix(matrix &t){memcpy(x,t.x,sizeof x);}
};
ll quick_pow(matrix a,int x){
  matrix ret;
  //初始化单位矩阵；
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      ret.x[i][j]=0;
    }
    ret.x[i][i]=1;
  }
  while(x){
    if(x&1) ret=ret*a;
    a=a*a;
    x>>=1;
  }
  ll ans=0;
  for(int i=0;i<k+2;i++)
  	ans+=ret.x[0][i]%mod;
  return ans;
}

ll C(int a,int b){
    if(b<0) return 0; 
    ll res = 1;
    for(int i = a,num = 1; num <= b; num++,i--) res *= i;
    for(int i = 1; i <= b; i++) res /= i;
    return res;
}
int main()
{
   int T;cin>>T;
   while(T--){
     cin>>n>>k;
     if(n==1) {cout<<1<<'\n';continue;}
     matrix m;
     m.x[0][0]=1;
     for(int i=1;i<k+2;i++)
     m.x[0][i]=C(k,i-1);

     for(int i=1;i<k+2;i++)
       	for(int j=0;j<k+2;j++)
           	m.x[i][j]=C(k-i+1,j-i);
     ll ans=quick_pow(m,n-1);
     cout<<ans%mod<<'\n';
   }
}

C : R??G??B??

题目描述

msy 的“显示器”终于完工啦！但是由于设计出了问题，这个“显示器”存在一个严重的 bug，就是每个像素同时只能显示红色、绿色、蓝色其中的一种颜色。msy 感觉一个学期白忙活了，但是又不能浪费材料，于是他觉得把这个有问题的“显示器”作为装饰。msy 喜欢蓝色和绿色，同时也喜欢偶数，因此他希望“显示器”的每一帧都同时包含偶数个蓝色像素和偶数个绿色像素。此时 msy 想知道，他可以看到多少不同的帧？ 由于答案可能很大，你只需输出答案对 998244353998244353 取模的结果即可。

输入格式

第一行一个数 T(1\le T\le 100)T(1≤T≤100)，表示数据组数。 接下来 TT 行，每行一个整数 n(1\le n\le 10^9)n(1≤n≤109)，表示“显示器”上的像素个数。

输出格式

输出 TT 行，表示每组数据的答案。

Input

6
1
2 
3
4
5
1000000000

Output

1
3
7
21
61
224965630

代码： 

#include<bits/stdc++.h>
using namespace std;
const int N = 3;
const int maxN = 1e9 + 2;
int T;
int n;
//long long A[maxN/2]; //蓝色和绿色都为偶数
//long long B[maxN/2]; //蓝色和绿色都为奇数
//long long C[maxN/2]; //蓝色和绿色有一个为奇数
//A[i] = A[i-1] + C[i-1];
//B[i] = B[i-1] + C[i-1];
//C[i] = 2*A[i-1] + 2*B[i-1] + C[i-1];
const long long p = 998244353;
struct Matrix{
    long long x[N][N];
    Matrix operator * (const Matrix& t) const{
        Matrix ret;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                ret.x[i][j] = 0;
                for(int k = 0; k < N; k++){
                    ret.x[i][j] += x[i][k] * t.x[k][j] % p;
                    ret.x[i][j] %= p;
                }
            }
        }
        return ret;
    }
    Matrix(){memset(x,0,sizeof x);}
    Matrix(const Matrix& t){memcpy(x,t.x,sizeof x);}
};
Matrix quick_pow(Matrix a,int x){
    Matrix ret;
    memset(ret.x,0,sizeof ret.x);
    ret.x[0][0] = ret.x[1][1] = ret.x[2][2] = 1;
    while(x) {
        if(x&1) ret = ret * a;
        a = a * a;
        x >>= 1;
    }
    return ret;
}
Matrix m1,m2;
long long f(){
    m1.x[0][0] = 1; m1.x[0][1] = 0; m1.x[0][2] = 1;
    m1.x[1][0] = 0; m1.x[1][1] = 1; m1.x[1][2] = 1;
    m1.x[2][0] = 2; m1.x[2][1] = 2; m1.x[2][2] = 1;
    m2 = quick_pow(m1,n-1);
    //A[1] = 1; B[1] = 0; C[1] = 2;
    cout << (m2.x[0][0] + m2.x[0][2] * 2)%p <<"\n";
    return m2.x[0][0];
}
int main(){
    cin >> T;
    for(int i = 0; i< T; i++){
        cin >> n;
        f();
    }
    return 0;
}

D : 衣柜

题目描述

ZJM 有 mm 件衬衫，现一共有 nn 天。 如果 ZJM 昨天穿衬衫 AA，今天穿衬衫 BB，则他今天可以获得 H[A][B] 快乐值。 询问 nn 天过后，ZJM 最多可以获得多少快乐值？

输入格式

第一行两个数 n,m(2\le n\le 10^8, 1\le m\le 100)n,m(2≤n≤108,1≤m≤100)，表示总天数和衬衫数量。 接下来 mm 行，每行 mm 个数，第 ii 行的第 jj 个数表示 Hi(0\le Hi\le 10^6)Hi(0≤Hi≤106)，即昨天穿衬衫 ii，今天穿衬衫 jj 可以获得的快乐值。

输出格式

输出一个数表示答案。

Input

3 2
0 1
1 0

Output

2

代码：

#include<bits/stdc++.h>
using namespace std;
int m,n; //m件衣服，n天
const int N = 102;
//long long f[100000008][102]; //f[i][j]第i天穿的衣服为j所获得的快乐
long long H[N][N];
//f[i][j] = max(f[i-1][k] +H[k][j]),1<=k<=M;
struct Matrix{
    long long x[N][N];
    Matrix operator * (const Matrix& t) const{
        Matrix ret;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                ret.x[i][j] = 0;
                for(int k = 0; k < m; k++){
                    ret.x[i][j] =max(ret.x[i][j],x[i][k] + t.x[k][j]);

                }
            }
        }
        return ret;
    }
    Matrix(){memset(x,0,sizeof x);}
    Matrix(const Matrix& t){memcpy(x,t.x,sizeof x);}
};
Matrix quick_pow(Matrix a,int x){
    Matrix ret;
    memset(ret.x,0,sizeof ret.x);
    while(x) {
        if(x&1) ret = ret * a;
        a = a * a;
        x >>= 1;
    }
    return ret;
}
int main(){
    cin >> n >> m;
    Matrix matrix1;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < m; j++)
            cin >> matrix1.x[i][j];
    Matrix matrix2 = quick_pow(matrix1,n-1);
    long long ans = 0;
    long long tempans = 0;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < m; j++)
            ans = max(ans,matrix2.x[i][j]);
    cout << ans;
    return 0;
}