一、第三周学习总结表

本周学习完成情况
Contest 完成情况
DFS练习 9/12
BFS练习 9/12
贪心算法练习 16/21
分治算法练习 16/16
二进制枚举算法练习 8/8
牛客喜迎暑假多校联赛第二场 6/9
Atcoder 3/8
总计 67/82
个人感悟
本周是暑期集训的第三周，学习了搜索，分治，贪心等基础的算法。学了这些算法之后，我明显的感受到了思考问题时有了更多的方向。但难就难在，很多题目往往并不是单考察这其中的某一种算法，而是很多算法和数据结构之间的交叉。本周学习的知识越来越难，能明显的感受到，每天的题目有时候并不能完全做完，只能做掉一部分，当天结束后，也没有把所有题目补完。而一种算法仅仅做了几道是十几道题目，我认为是完全不够的。所以对于算法还有待做更多的训练去熟练，对不同算法之间的交叉，有待去总结规律，去总结注意的细节。另外在做题目时，不能因为看到标题为xx算法练习赛，就只往一个xx算法一个方向去思考，毕竟比赛的时候没有人会提醒你这用的是什么算法。

在本周的训练里，我发现了在学习之中可以发散开去学习。比如在贪心算法的食堂买饭问题里，我了解到了动态规划算法，那题需要先用贪心想到解决方法，再转换为背包问题，计算剩下的问题。这道问题引起了我的好奇也补充了我对背包问题的初步认识。而背包问题仅仅只是动态规划算法的其中一部分，整个动态规划又包含了像区间DP，状态压缩DP等高级算法，有待未来的日子里加强对这些算法的训练

Contest	完成情况
DFS练习	9/12
BFS练习	9/12
贪心算法练习	16/21
分治算法练习	16/16
二进制枚举算法练习	8/8
牛客喜迎暑假多校联赛第二场	6/9
Atcoder	3/8
总计	67/82

二、本周学习新内容

1.bitset

一个容器可以直接操作一个数的二进制形式

bitset<n> s n位二进制数

基本操作：

~每一位取反
& | ^两个相同位数的进行按位运算
<< >>返回一个bitset左/右移若干位的结果

容器方法：

s.count()返回1的个数
s.any()所有位都为0 返回false. 有一位是1 返回true
s.none()所有位都为0 返回true. 有一位是1 返回false
s.set()所有位都变1 s.reset()所有位都变为0
s[n]=1/0直接操作第几位

2.scanf

scanf(“%1d”,&a);控制输入数字的位数

3.c++的数学函数

$e^x$即exp(x)

$ln(x)$即log(x)

$lg(x)$即log10(x)

$log_ab$需要用到换底公式

如$log_28$即log(8)/log(2)

$a^b$可以转换为$e^{blna}$，也就是exp(b*log(a))

4.setw(n)

右对齐

5.基姆拉尔森计算公式

$W= (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400+1)MOD7$

6.二进制枚举

即运用二进制的特殊性质，每一个数都可以转换成01所组成的数

而0和1可以作为判断的条件

那么对于有n个数的集合，共有2^n^个子集

事实上每个子集都是对于该集合的第i个元素选择或者不选产生的结果

那么面对集合的子集的问题是，往往可以用二进制枚举的方法

#include <bits/stdc++.h>
using namespace std;
void print_subset(int n){
     for(int i=0; i< (1<<n); i++) {
   		//i：0~2^n，每个i的二进制数对应一个子集。
		for(int j=0;j<n;j++)//打印一个子集，即打印i的二进制数中所有的1的位数
           if(i & (1<<j))//1<<j，意思是，1向左移动j位，移动以后再和i做&运算，如果i的第j位为1，就会判定成真
               cout<< j << " ";
       	cout << endl;
    }
}
int main(){
    int n;
    cin>>n;           // n：集合中元素的总数量。
    print_subset(n);  // 打印所有的子集。
}

7.深搜与广搜

深搜的注意点：

注意是dfs函数的参数：如果把结果/新的状态带入dfs，进行下一步搜索，那么回溯时不需要进行撤销操作，因为下一步操作会自动的覆盖掉，而且每次都是用新的数组去搜索，不会对当前状态产生影响，但是使用原数组进行操作/进行标记的时候一定要记得回溯的时候，要撤销原来的标记
变量的设置：通常将变量设置为全局变量，这样可以dfs的时候直接使用，但是如果遇到多组数据测试，一定要在每次测试之前将数据清零初始化。如max，cnt等等
剪枝操作：剪枝是进行dfs的重要的考虑条件，通常题目不会那么直白，不剪枝则会超时。
关于回溯：如果只需要一种条件，那么得到答案的时候，可以设置一个变量，判断是否已经得出结果。通常这个判断放在dfs的下面，也就是回溯的出口。以及判断是否到达终点的下面，避免到达终点后还继续下一步。

广搜的注意点：

注意顺序：注意压入队列操作，弹出队列，判断是否能压入队列操作的顺序。如先把数压入队列，等到把他弹出来，判断是否可以扩展的时候，再进行判断，就会导致出现死循环。
注意进行标记：不然会造成重复压入队列，造成死循环

8.快读

inline int read(){
    register int x = 0, t = 1;
    register char ch=getchar(); // 读入单个字符到寄存器
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);  // 移位与异或
      	// 第十行可以换成 x = x * 10 + ch - '0'
        ch=getchar();
    }
    return x*t;
}

9.动态规划

动态规划可以分为五个部分

确定dp数组（dp table）以及下标的含义
确定递推公式，找出最优子结构
dp数组如何初始化
确定遍历顺序
举例推导dp数组

01背包问题

每个物品只有选与不选

那么对于dp[n个物品][容量]=max(dp[n-1个物品][容量],dp[n-1个物品][容量]+weight[j])

多重背包就是再用一个k数组，枚举物品的数量即可

三、题解一览

1.DFS - C - Network Saboteur

题目标签

DFS

题目描述

给定一堆不同的点，以及每个点之间的距离

给定两个集合，集合中容纳的点的数量无限

只有当两个点处于不同的集合之中时，才有距离

现在请你求出所有的距离的最大值

题目解析

点的最大数量为20，每个点存在的集合要么A，要么B，只有两种选择

如果枚举所有的情况，运算的最大次数为2^20^没有超过时间范围。

所以这题可以直接使用dfs暴力搜索

可以先初始化，假定所有的点都在集合A之中

定义一个bool类型，储存了每个点是否在A中。每层搜索都有两种结果。

分别对和进行计算，求出最大的和即可

通过代码

#include<bits.stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
//先把所有都放进A集合，然后再遍历每个点，每个点都有两种选择，留在A，放进B
//每个点的选择，都求一次和，然后取最大值
int dis[21][21];//每个两个点之间的距离
int n;
int maxdis=-1;
bool isInA[21];//代表每个点是否在A里面
void dfs(int cur,int sum){
    maxdis=max(maxdis,sum);
    if (cur==n+1)
    {
        return;
    }
    //第cur个点离开A,进入B
    isInA[cur]=false;
    int temp=0;
    for (int i = 1; i <= n; i++)
    {
        if (isInA[i])
        {
            temp+=dis[i][cur];
        }else{
            temp-=dis[i][cur];
        }
    }
    dfs(cur+1,sum+temp);
    isInA[cur]=true;
    dfs(cur+1,sum);
}
int main()
{
    cin>>n;
    //初始化，所有点每个点都先假设在A里面
    for (int i = 1; i <= n; i++)
    {
        isInA[i]=true;
    }
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin>>dis[i][j];
        }
        
    }
    dfs(1,0);
    cout<<maxdis;
}

2.DFS - D - Shredding Company

题目标签

dfs

题目描述

公司发明了一种碎纸机，对一个数字，可以进行不限次数的裁剪

如123454 可以裁剪为1 23 45 4

对裁剪后的数进行求和，求和不超过给定的目标值的最大值时多少

题目解析

对每个间隔有剪和不剪两种选择，分别进行dfs

并把切下来的数先存到一个数组里面

切下来的数，就变为0，以便下次不会重复切取

到数字是最后一个的时候，计算和，并保留最大值

剪枝：已有数组已经有数大于目标值

注意：最后一位，不能不切。结尾要输出正确的切法。那么每次有最大值的时候，就用anscopy数组把储存的裁切数组拷贝一下

通过代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
int target;
string s;
//判断条件：必须小于等于
//对字符串进行分割，每一个间隔选择切or不切进行dfs.
//切的话，加上sum，然后传递剩下的字符串
//求和判断
//剪枝：已有数组已经有数大于目标值
int chage(string s){
    int sum=0;
    for (int i = 0; i < s.length(); i++)
    {
        sum=sum*10+(s[i]-'0');
    }
    return sum;
}
void cut(string &s,int cur){
    for (int i = 1; i <= cur; i++)
    {
        s[i]='0';
    }
}
int maxans=-1;
int ansnum=0;
vector<int> ans;
vector<int> anscopy;//储存结果，dfs回溯之后ans不会保留
void dfs(int cur,string now,int sum,int len){
    if(sum>target) return;
    if(cur==len+1){
        if (maxans<sum)
        {   
            maxans=sum;
            ansnum=1;
            anscopy=ans;
        }else if(maxans==sum){
            ansnum++;
        }
        return;
    }
    //切
    string temp=now.substr(1,cur);//取切掉的
    int tempnum=chage(temp);//取切下来的
    ans.push_back(tempnum);
    string newnow=now;
    cut(newnow,cur);//把切了的变0，下次切就不会取数
    int newsum=sum+tempnum;
    dfs(cur+1,newnow,newsum,len);
    //不切
    ans.pop_back();
    if(cur<len){//最后一位不能不切了
        dfs(cur+1,now,sum,len);
    }
}
int main()
{
    int t=0;
    while (cin>>target>>s && target!=0 && s!="0")
    {
        anscopy.clear();
        ans.clear();
        maxans=-1;
        ansnum=0;
        
        if (t++!=0) cout<<endl;
        if (chage(s)==target)
        {
            cout<<s<<" "<<target;
            continue;
        }
        int len=s.length();
        s="0"+s;//占位符，让下标从1开始
        dfs(1,s,0,len);
        if (ansnum==1)
        {
            cout<<maxans;
            for (int i = 0; i < anscopy.size(); i++)
            {
                cout<<" ";
                cout<<anscopy[i];
            }
        }else if(ansnum>1){
            cout<<"rejected";
        }else if (ansnum==0)
        {
            cout<<"error";
        }
    }
    return 0;
}

3.DFS - E - Sudoku

题目标签

DFS

题目描述

给定一个9*9的数独

0代表空的

输出一种解

题目解析

dfs爆搜

用三个数组分别保存了第n行的k是否可填。第n列的k是否可填，第i，j个小方格是否可填

一个一个点的搜索，如果该点已经有数，那么就搜索下一个数。如果没有就枚举每个可以的数

当到达最后一个点的next点后，回溯。并再回溯的地方增加判断回溯的条件，达到快速回溯的目的

注意：

回溯的时候，要把数字变回0
把该点的某个数变回可以填
判断小方格是否可以填写的是isMatrixValid[(row+2)/3][(col+2)/3][value]=true;
这样可以把三个数归为一

通过代码

#include<bits/stdc++.h>
using namespace std;
int num[10][10];
const double PI = acos(-1.0);
//用数组标记该行的数哪些可以填，每次填数都进行一个check操作
//check不仅包括行和列，3*3的小格子是难点
//用num[10][10]来记录填了哪些数
//如果遇到填过了，就跳过，没填就依次挑选，依次check。可以填就填，然后dfs下一个点
bool isRowValid[10][10];//记录行的某个数是否可以填
bool isColValid[10][10];//记录列的某个数是否可以填
bool isMatrixValid[4][4][10];//记录第i,j个小方格能否填
bool check(int row,int col,int value){
    if (isRowValid[row][value]==true && isColValid[col][value]==true)
    {
        if(isMatrixValid[(row+2)/3][(col+2)/3][value]==true){//小方格
            return true;
        }
    }
    return false;
}
void next(int &row,int &col){//下一个点
    if (col==9)
    {
        row++;col=1;
    }else{
        col++;
    }
}
bool ok=false;
void dfs(int row,int col)
{
    if (row==10)//完成
    {
        ok=true;
        return;
    }
    if (num[row][col]>0)//填了
    {
        int newrow=row,newcol=col;
        next(newrow,newcol);
        dfs(newrow,newcol);
        if(ok==true){
            return;
        }
    }else{
        for (int value = 1; value <= 9; value++)
        {
            if (check(row,col,value)==true)
            {
                num[row][col]=value;
                isRowValid[row][value]=false;
                isColValid[col][value]=false;
                isMatrixValid[(row+2)/3][(col+2)/3][value]=false;
                int newrow=row,newcol=col;
                next(newrow,newcol);
                dfs(newrow,newcol);
                if(ok==true){
                    return;
                }
                num[row][col]=0;
                isRowValid[row][value]=true;
                isColValid[col][value]=true;
                isMatrixValid[(row+2)/3][(col+2)/3][value]=true;
            }
            
        }
        if(ok == false){
            
            return;
        }
    }
    
}
int main()
{
    int n;
    cin>>n;
    char c=getchar();//读换行
    while (n--)
    {
        //初始化
        for(int i=1;i<=9;i++){
            for(int value=1;value<=9;value++){
                isRowValid[i][value]=true;
                isColValid[i][value]=true;
            }
        }
        for(int i=1;i<=3;i++){
            for(int j=1;j<=3;j++){
                for(int value=1;value<=9;value++){
                    isMatrixValid[i][j][value]=true;
                }
            }
        }
        ok=false;

        
        //输入
        for (int i = 1; i <= 9; i++)
        {
            for (int j = 1; j <= 9; j++)
            {
                char temp=getchar();
                int value=(temp-'0');
                num[i][j]=value;
                isRowValid[i][value]=false;
                isColValid[j][value]=false;
                isMatrixValid[(i+2)/3][(j+2)/3][value]=false;
            }
            getchar();//读换行
            
        }

        dfs(1,1);

        //输出
        for (int i = 1; i <= 9; i++)
        {
            for (int j = 1; j <= 9; j++)
            {
                cout<<num[i][j];
            }
            cout<<endl;
        }
        
    }
}

4.Set Operation

题目标签

bitset的使用

题目描述

给定n个集合

每个集合中有c个数

接下来给定q个询问

每个询问包含两个数，对于所有的n个集合，判定是否两数在一个集合中

题目解析

对于每一个数，记录他存在的所有集合

对于查询的数a,b只要查询他们所存在过的集合有没有交集即可

如果每个数存在的集合用map+vector来储存，求交集必然会超时

所以这时候bitset就是一个很好的选择

可以用一个数来作为标记，很好的进行了状态压缩

比如7——1101也就是代表在第1，3，4个集合中出现过

而bitset支持单个位数的修改，还能保证占用的空间小

同时求交集只需要将两个数的bitset 进行按位与操作&。

某一位都为1才会保留，也就是都存在过一个集合里就会保留

然后统计他们与的结果里的1个个数是否>0即可

使用bitset自带的count()方法

通过代码

#include<bits.stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
//st[i][j]表示i存在的集合
//[j]为桶
int main()
{
    ll t;scanf("%lld",&t);
    bitset<1000> mp[10005];
    for (ll i = 0; i < t; i++)
    {
        ll num;
        scanf("%lld",&num);
        for (ll j = 0; j < num; j++)
        {
            ll temp;
            scanf("%lld",&temp);
            mp[temp][i]=1;//第temp个数的第i位变1
        }
    }
    ll q;scanf("%lld",&q);
    for (ll i = 0; i < q; i++)
    {
        ll a,b;
        scanf("%lld %lld",&a,&b);
        bitset<1000> t=mp[a]&mp[b];
        if(t.count()==0){
            printf("No\n");
        }else{
            printf("Yes\n");
        }
    }
    
    return 0;
}

5.BFS - D - Prime Path

题目标签

bfs

题目描述

给你一个素数，和目标数

要求每次改一个位上的数

要求转换完的数也是素数

求最终转换成目标数需要的最少次数

题目解析

bfs广搜

先打素数表

每个数，变换每个位置的数

判断是否位素数

是的话加入，记录当前数经过变换的次数

对进入过队列的数要标记

通过代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 500005
#define inf 1000000007
using namespace std;
const double PI = acos(-1.0);
bool isprime[maxn];
int prime[maxn];
void Euler(int n)
{
    int t = 0;
    for (int i = 2; i <= n; i++)
    {
        isprime[i] = true; // 2-n初始化
    }
    for (int i = 0; i <= n; i++)
    {
        if (isprime[i])
        {
            prime[t++] = i;
        }
        for (int j = 0; j < t && i * prime[j] <= n; j++)
        {
            //判断条件j不能超过现有质数的个数，且相乘即被筛的数不能越上界
            isprime[prime[j] * i] = false;
            if (i % prime[j] == 0)
            { //解析详见下文
                break;
            }
        }
    }
}
int main()
{
    //打质数表
    Euler(10000);
    int src, dst;
    int t;
    cin >> t;
    while (t--)
    {
        map<int, int> mp;
        map<int, int> vis;
        cin >> src >> dst;
        queue<int> q;
        q.push(src);
        mp[src] = 0;
        vis[src]=true;
        while (!q.empty())
        {
            int curnum = q.front();
            if (curnum == dst)
            {
                cout << mp[curnum] << endl;
                break;
            }
            for (int i = 1; i <= 9; i += 2)
            {
                int newnum = curnum / 10 * 10 + i;
                if (isprime[newnum] && !vis[newnum])
                {
                    q.push(newnum);
                    mp[newnum]=mp[curnum]+1;
                    vis[newnum] = true;
                }
            }
            for (int i = 0; i <= 9; i++)
            {
                int newnum = curnum / 100 * 100 + i * 10 + curnum % 10;
                if (isprime[newnum] && !vis[newnum])
                {
                    q.push(newnum);
                    mp[newnum]=mp[curnum]+1;
                    vis[newnum] = true;
                }
            }
            for (int i = 0; i <= 9; i++)
            {
                int newnum = curnum / 1000 * 1000 + i * 100 + curnum % 100;
                if (isprime[newnum] && !vis[newnum])
                {
                    q.push(newnum);
                    mp[newnum]=mp[curnum]+1;
                    vis[newnum] = true;
                }
            }
            for (int i = 1; i <= 9; i++)
            {
                int newnum = i * 1000 + curnum % 1000;
                if (isprime[newnum] && !vis[newnum])
                {
                    q.push(newnum);
                    mp[newnum]=mp[curnum]+1;
                    vis[newnum] = true;
                }
            }
            q.pop();
        }
    }
}

5.BFS - D - Prime Path

题目标签

bfs

题目描述

给你两杯水A.B

你可以进行三种操作

把A，B中的一杯填满
把A，B中的一杯倒掉
把A倒入B/B倒入A

给出三个数分别为

A的容量 B的容量目标容量

求需要多少步，可以达到最终的容量。

并输出这些步骤

如果不可能则输出”impossible”

题目解析

BFS广搜即可

队列加入的是一个状态

用struct来定义

定义的struct包含

A的水量
B的水量
经过的步骤

注意点：

要用vis数组，对已经产生过的AB的水量进行标记，避免重复进行，无法走出循环
经过的步骤可以用vector来储存，最终输出的时候再转换

通过代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
//储存的是一个自定义的结构体，即当前的状态
//此外还要储存一个字符串数组，记录的时当前状态已经做了哪些操作
int fulA,fulB,dst;

struct state{
    int A;
    int B;
    int step;
    vector<int> op;
    state(int a,int b,int stp){
        A=a;
        B=b;
        step=stp;
    }
    state(void){
        A=0;
        B=0;
        step=0;
    }
};

string ans[7]={"","FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};

void print(const vector<int>& v){
    cout<<v.size()<<endl;
    for (int i = 0; i < v.size(); i++)
    {
        if(i!=0) cout<<endl;
        cout<<ans[v[i]];
    }
}

int main()
{
    bool vis[1000][1000]={false};
    cin>>fulA>>fulB>>dst;
    queue<state> q;
    state s(0,0,0);
    vis[0][0]=true;
    q.push(s);

    while (!q.empty())
    {
        state curState = q.front();
        if (curState.A==dst || curState.B==dst)
        {
            print(curState.op);
            return 0;
        }

        //三种选择2种方案
        //fill A
        state newState1(fulA,curState.B,curState.step+1);
        newState1.op=curState.op;
        newState1.op.push_back(1);
        if(vis[newState1.A][newState1.B]!=true){
            q.push(newState1);
            vis[newState1.A][newState1.B]=true;
        }
        //fill B
        state newState2(curState.A,fulB,curState.step+1);
        newState2.op=curState.op;
        newState2.op.push_back(2);
        if(vis[newState2.A][newState2.B]!=true){
            q.push(newState2);
            vis[newState2.A][newState2.B]=true;
        }
        //Drop A
        state newState3(0,curState.B,curState.step+1);
        newState3.op=curState.op;
        newState3.op.push_back(3);
        if(vis[newState3.A][newState3.B]!=true){
            q.push(newState3);
            vis[newState3.A][newState3.B]=true;
        }
        //Drop B
        state newState4(curState.A,0,curState.step+1);
        newState4.op=curState.op;
        newState4.op.push_back(4);
        if(vis[newState4.A][newState4.B]!=true){
            q.push(newState4);
            vis[newState4.A][newState4.B]=true;
        }

        //Pour A to B
        //A>B 剩下的， B加满
        int newA,newB;
        if (curState.A>=fulB-curState.B)
        {
            newB=fulB;
            newA=curState.A-(fulB-curState.B);
        }
        //A<B 剩下的， B+A A=0
        if (curState.A<fulB-curState.B)
        {
            newA=0;
            newB=curState.B+curState.A;
        }
        state newState5(newA,newB,curState.step+1);
        newState5.op=curState.op;
        newState5.op.push_back(5);
        if(vis[newState5.A][newState5.B]!=true){
            q.push(newState5);
            vis[newState5.A][newState5.B]=true;
        }

        //Pour B to A
        //A>B 剩下的， B加满
        if (curState.B>=fulA-curState.A)
        {
            newA=fulA;
            newB=curState.B-(fulA-curState.A);
        }
        //A<B 剩下的， B+A A=0
        if (curState.B<fulA-curState.A)
        {
            newB=0;
            newA=curState.A+curState.B;
        }
        state newState6(newA,newB,curState.step+1);
        newState6.op=curState.op;
        newState6.op.push_back(6);
        if(vis[newState6.A][newState6.B]!=true){
            q.push(newState6);
            vis[newState6.A][newState6.B]=true;
        }
        q.pop();
    }
    cout<<"impossible";
    
}

5.贪心 - D - Prime Path

题目标签

贪心

题目描述

有n档节目，每档节目有开始时间和结束时间

求最多能看完整的节目

题目解析

经典的区间调度问题

因为求的是最多，所以要把节目按照结束的时间来排序

遍历每一个节目，如果下一个节目的开始时间晚于上一个节目的结束时间

那么cnt++

将当前选择的节目更新

通过代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
const double PI = acos(-1.0);
bool flag=false;
struct act
{
    int start;
    int end;
};
bool cmp(act a,act b){
    if (a.end!=b.end) return a.end<b.end;
    return a.start<b.start;
    
}
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // freopen("3output.out","w",stdout);
    // freopen("1input.in","r",stdin);
    int sum=0;
    int n;
    while (cin>>n && n!=0)
    {
        sum=0;
        act a[101];
        for (int i = 0; i < n; i++)
        {
            cin>>a[i].start>>a[i].end;    
        }
        sort(a,a+n,cmp);
        int nowend=a[0].end;
        sum+=1;
        for (int i = 1; i < n; i++)
        {
            if (a[i].start>=nowend)//下一个活动的时间，开始晚于上一个活动的结束时间
            {
                sum++;
                nowend=a[i].end;//选下一个活动
            }
        }
        cout<<sum<<endl;
    }
    // printf("Time used = %.2lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

6.贪心 - E - Doing Homework again

题目标签

贪心

题目描述

小明有n个作业，没有做完

每个作业有相应的分值和截止日期

规定如果某个作业没有在截止日期之前写完，就会扣除相应的分值

请你计算小明扣分最少为多少

题目解析

贪心+日程安排

将所有作业按照分值从大到小来做，尽量把这个作业做的时间靠近他的截止日期的时间

以便把前面的时间留出来做其他作业

分值相同的按照截止日期排名，靠前的排在前面

用一个vis数组来记录当天的日程有没有被安排

先按分值大的来计算，查看他的截止日期那天有没有安排

没有安排，那么就安排在那天。

有安排就往前排，实在没有那就不做

不用担心被扣分，因为如果没有安排的话，说明被安排的都是分值比他大的

所以扣分一定是最小的

通过代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
bool flag=false;
struct work
{
    int time;
    int score;
    bool vis=false;
};
bool cmp(work a,work b){
    if(a.score!=b.score){
        return a.score>b.score;
    }
    return a.time<b.time;
}
//转化为日程安排问题
//总共n天，从大到小分值进行安排。
//第i个作业，如果原本是第timei天完成，那么就timei完成。如果那天被占，就从后往前安排
//反正是分大的，就算占用了同样本来是这天完成的作业，也没有关系
//vis来记录是否已经完成，最后统计所有没有完成的作业。然后逐个扣分
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // freopen("3output.out","w",stdout);
//     freopen("1input.in","r",stdin);
    int t;cin>>t;
    while (t--)
    {
        int day[1001]={0};
        int n;cin>>n;
        work w[1001];
        for (int i = 0; i < n; i++) cin>>w[i].time;
        for (int i = 0; i < n; i++) cin>>w[i].score;
        sort(w,w+n,cmp);
        int sum=0;
        for (int i = 0; i < n; i++)
        {
            if (day[w[i].time]==0)//没有安排
            {
                day[w[i].time]=1;
                w[i].vis=true;
            }else{//从后往前
                for (int j = w[i].time-1; j >= 1; j--)
                {
                    if (day[j]==0)//从后往前的没有安排
                    {
                        day[j]=1;
                        w[i].vis=true;
                        break;//找到了就及时推出，不然一直循环下去把所有日子都占了
                    }
                }
                //没有找到空的，不安排，扣分
            }
        }
        for (int i = 0; i <n; i++)
        {
            if (w[i].vis==false)
            {
                sum+=w[i].score;
            }
        }
        cout<<sum<<endl;   
    }
    return 0;
}

7.饭卡

题目标签

贪心；背包dp

题目描述

有一张饭卡，当他大于等于五块钱的时候，购买一个东西不管钱够不够，一定能买成功

现在你的饭卡里有x元

共有n个菜

每道菜的价格为ai元

求饭卡最低能花到多少钱

题目解析

要让饭卡最低，肯定要最贵的菜在只有五块钱的时候买

那么接下来就转化成一个01背包的问题

只要让x-5元尽可能被花光即可

通过代码

#include<bits/stdc
#define ios ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
const double PI = acos(-1.0);
//排序出最贵的菜，等到用的只有五块的时候再用
//前n-1个菜就转化为01背包问题
//如果钱的总数已经大于菜的总数，那么直接输出，不用再计算
int main()
{
    int n;
    while (cin>>n && n!=0)
    {
        int value[2000]={0};
        int sum=0;
        for (int i = 0; i < n; i++)
        {
            cin>>value[i];
            sum+=value[i];
        }
        int cap;
        cin>>cap;
        if(cap-sum>=0){
            cout<<cap-sum<<endl;
            continue;
        }
        if(cap<5){
            cout<<cap<<endl;
            continue;
        }
        sort(value,value+n);
        //dp前n-1个菜，每个菜的容量是value[i]，价值也是value[i]
        int dp[2000]={0};//dp[j]：表示，用j块钱能花的最多的菜
        for (int i = 0; i < n-1; i++)
        {
            for (int j = cap-5; j >=value[i]; j--)
            {
                dp[j]=max(dp[j],dp[j-value[i]]+value[i]);
            }
            
        }
        cout<<cap-dp[cap-5]-value[n-1]<<endl;
    }
    return 0;
}

8.贪心 - H - Coins

题目标签

贪心

题目描述

现在有1，5，10，50，100元的纸币各若干张，需要用这些纸币去支付C元。
最多需要多少张纸币？最少需要多少张纸币？

题目解析

最少需要的纸币，从大到小选择即可

最多需要的纸币可以利用逆向思维，即求最少能剩下的纸币即可

通过代码

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
const double PI = acos(-1.0);
bool flag=false;
//没有输出-1
int main()
{
    ll T;cin>>T;
    while (T--)
    {
        ll maxn=0;ll minn=0;
        ll dst,y1,y5,y10,y50,y100;
        cin>>dst>>y1>>y5>>y10>>y50>>y100;
        ll all=y1+y5*5+y10*10+y50*50+y100*100;
        ll redst=dst;
        //求最少从大到小贪心
        if(all<dst){
            cout<<"-1 -1"<<endl;
            continue;;
        }
        if(dst/100<=y100){
            maxn+=dst/100;
            dst-=(dst/100)*100;
        }else{
            maxn+=y100;
            dst-=y100*100;
        }

        if(dst/50<=y50){
            maxn+=dst/50;
            dst-=(dst/50)*50;
        }else{
            maxn+=y50;
            dst-=y50*50;
        }

        if(dst/10<=y10){
            maxn+=dst/10;
            dst-=(dst/10)*10;
        }else{
            maxn+=y10;
            dst-=y10*10;
        }

        if(dst/5<=y5){
            maxn+=dst/5;
            dst-=(dst/5)*5;
        }else{
            maxn+=y5;
            dst-=y5*5;
        }
        
        if(dst/1<=y1){
            maxn+=dst/1;
            dst-=(dst/1)*1;
        }else{
            maxn+=y1;
            dst-=y1*1;
        }
        if(dst==0){
            cout<<maxn<<" ";
        }else{
            cout<<"-1 ";
        }
        dst=all-redst;
        maxn=0;
        //求最少从大到小贪心
        if(dst/100<=y100){
            maxn+=dst/100;
            dst-=(dst/100)*100;
        }else{
            maxn+=y100;
            dst-=y100*100;
        }

        if(dst/50<=y50){
            maxn+=dst/50;
            dst-=(dst/50)*50;
        }else{
            maxn+=y50;
            dst-=y50*50;
        }

        if(dst/10<=y10){
            maxn+=dst/10;
            dst-=(dst/10)*10;
        }else{
            maxn+=y10;
            dst-=y10*10;
        }

        if(dst/5<=y5){
            maxn+=dst/5;
            dst-=(dst/5)*5;
        }else{
            maxn+=y5;
            dst-=y5*5;
        }
        if(dst/1<=y1){
            maxn+=dst/1;
            dst-=(dst/1)*1;
        }else{
            maxn+=y1;
            dst-=y1*1;
        }
        minn=y1+y5+y10+y50+y100-maxn;
        if(dst==0){
            cout<<minn<<endl;
        }else{
            cout<<"-1 "<<endl;
        }
    }
}

9.分治练习 - A - Inversion

题目标签

分治

题目描述

给定一个序列，和你可以进行的交换的次数

每次交换只能交换相邻的两位数字

求最少的逆序对

题目解析

每次交换只能交换相邻的，那么每次交换最多只能消除一个逆序对

所以只要先求总的逆序对，再减去交换的次数即可

求总逆序对的方法：在归并排序的同时，如果遇到逆序的元素，那就ans++

归并排序的方法：

先不断的二分，直到分为两个数

然后把开一个新的数组

把左右两个序列中的数正确的排到新的序列里面

每次放进去的时候事先比较，在两个数的大小

如果左序列的数大于有序列，说明产生逆序

此时需要ans+=mid-i+1

即把有序列中的那个数后面的数也算进答案中

因为当前的序列一定是上一个序列中已经排好的，所以比当前左序列的数还要大的数，肯定也比有序列当前的数大

所以逆序对这个变量都要把他们记录

通过代码

#includeM<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
/**归并排序
 * 先拆分，拆到两数字相同了，开始比较，两个区间的，如果有逆序对，记录
 * 完事了要合并
 **/
ll ans=0;
int n,num[5000001], temp[5000001];
void mergesort(int l, int r)//归并排序
{
	int mid = (l + r) / 2;//取中间 
	if(l == r)//若l == r了，就代表这个子序列就只剩1个元素了，需要返回 
	{
		return;
	}
	else
	{
		mergesort(l, mid);//分成l和中间一段，中间 + 1和r一段（二分） 
		mergesort(mid + 1, r);
	}
	int i = l;//i从l开始，到mid，因为现在排序的是l ~ r的区间且要二分合并 
	int j = mid + 1;//j从mid + 1开始，到r原因同上
	int t = l;//数组b的下标，数组b存的是l ~ r区间排完序的值 
	while(i <= mid && j <= r)//同上i，j的解释 
	{
		if(num[i] > num[j])//如果前面的元素比后面大(l ~ mid中的元素 > mid + 1 ~ r中的元素
		{ 
			ans += mid - i + 1;
			temp[t++] = num[j];
			++j;
		}
		else
		{
			temp[t++] = num[i];//i小，存a[i] 
			++i;//同理 
		}
	}
	while(i <= mid)//把剩的元素(因为较大所以在上面没选) 
	{
		temp[t++] = num[i];//存进去 
		++i; 
	}
	while(j <= r)//同理 
	{
		temp[t++] = num[j];
		++j;
	}
	for(register int i = l; i <= r; ++i)//把有序序列b赋值到a里 
	{
		num[i] = temp[i];
	}
	return;
}
int main()
{
	int cnt=0;
	while (cin>>n>>cnt)
	{
		ans=0;
		for (int i = 0; i < n; i++)
		{
			cin>>num[i];
		}
		mergesort(0,n-1);
		if(ans-cnt>0){
			cout<<ans-cnt;
		}else{
			cout<<0;
		}
		cout<<endl;
	}
    return 0;
}

10.分治 - F - Building for UN

题目标签

思维

题目描述

有一个大厦，大厦中有n个国家

左右相邻上下相邻以及在同一位置上下楼也算相邻

求一种排布方式，使得每两个国家之间的办公室都有相邻

题目解析

只需要两层

第一层第i行全是国家ai

第二层第j列全是国家aj

即

AAAA
BBBB
CCCC
DDDD

ABCD
ABCD
ABCD
ABCD

通过代码

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
int main()
{
    string ss="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    int n;
    while (cin >> n)
    {
        cout << 2 << " " << n << " " << n << endl;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cout<<ss[i];
            }
            cout<<endl;
        }
        cout<<endl;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cout<<ss[j];
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}

11.分治 - H - Wine trading in Gergovia

题目标签

贪心

题目描述

有n个酒馆

每个酒馆可以卖酒也可以买酒

并且他们的需求和产出之和一定为0

但是运酒需要花费劳动力

劳动力为酒的数量

求出最少的劳动力，是所有的酒馆都能买到所有需求的酒和卖掉所有需求的酒

题目解析

其实是一道贪心问题、

不管每个酒馆是买酒还是卖酒，只要从第1个酒馆开始

把当前酒馆所有的能卖的都搬到下一个酒馆即可

通过代码

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
//常量，就是pi
const double PI = acos(-1.0)
int main()
{
    ll n;
    while (cin >> n && n!=0)
    {
        ll num[n];
        for (ll i = 0; i < n; i++)
        {
            cin >> num[i];
        }
        ll ans = 0;
        for (ll i = 0; i < n - 1; i++)
        {
            ans += abs(num[i]);
            num[i + 1] += num[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

12.牛客喜迎暑假多校联赛 - D - N数之和

题目标签

快读

题目描述

读入n个数，求和

题目解析

直接做会超时，必须用快读

快读要用getchar() 一个一个字符的读入并计算

通过代码

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
const double PI = acos(-1.0);
int main()
{
    ll n;scanf("%lld",&n);
    getchar();
    ll sum=0;
    while(n--){
        ll temp=0;
        char c;
        while ((c=getchar())!=' ' && c!='\n')
        {
            temp=temp*10+(c-'0');
        }
        sum+=temp;
    }
    printf("%lld",sum);
    return 0;
}

22暑期ACM集训周记03

一、第三周学习总结表

本周学习完成情况

个人感悟

二、本周学习新内容

1.bitset

2.scanf

3.c++的数学函数

4.setw(n)

5.基姆拉尔森计算公式

6.二进制枚举

7.深搜与广搜

深搜的注意点：

广搜的注意点：

8.快读

9.动态规划

三、题解一览

1.DFS - C - Network Saboteur

题目标签

题目描述

题目解析

通过代码

2.DFS - D - Shredding Company

题目标签

题目描述

题目解析

通过代码

3.DFS - E - Sudoku

题目标签

题目描述

题目解析

通过代码

4.Set Operation

题目标签

题目描述

题目解析

通过代码

5.BFS - D - Prime Path

题目标签

题目描述

题目解析

通过代码

5.BFS - D - Prime Path

题目标签

题目描述

题目解析

通过代码

5.贪心 - D - Prime Path

题目标签

题目描述

题目解析

通过代码

6.贪心 - E - Doing Homework again

题目标签

题目描述

题目解析

通过代码

7.饭卡

题目标签

题目描述

题目解析

通过代码

8.贪心 - H - Coins

题目标签

题目描述

题目解析

通过代码

9.分治练习 - A - Inversion

题目标签

题目描述

题目解析

通过代码

10.分治 - F - Building for UN

题目标签

题目描述

题目解析

通过代码

11.分治 - H - Wine trading in Gergovia

题目标签

题目描述