Skip to content

Latest commit

 

History

History
1255 lines (1129 loc) · 25 KB

ccf csp 材料.md

File metadata and controls

1255 lines (1129 loc) · 25 KB
Raw

常用函数与stl

reverse(v.begin(),v.end()); //翻转（逆序）
sort(v.begin(),v.end());
swap(nums[i], nums[ptr]); //交换函数
max(merged.back()[1], R); //大小比较选取
max_element(myvector.begin(),myvector.end());//返回向量中最大元素的迭代器，注意返回的是迭代器，头文件是algorithm
reverse(ans.begin(), ans.end());//答案反转
rand函数，C语言中用来产生一个随机数的函数。
int a = round(11.5); //四舍五入，得到a=12
sqrt(5); //根号5
pow(a,2); //a的平方
num = abs(num);//取绝对值，abs是针对于int类型的
//distance() 函数用于计算两个迭代器表示的范围内包含元素的个数
rand();  //返回一个从0到最大随机数的任意整数
int result = accumulate(nums.begin(), nums.end(), 0);//序列求和

vector<int> v{ 4, 7, 9, 1, 2, 5 };
int key = 2;
if (count(v.begin(), v.end(), key)){
	cout << "Element found" << endl;
}

if (std::find(v.begin(), v.end(), key) != v.end())
if (std::find_if(v.begin(), v.end(), [] (int i) { return i < 3 && i > 1 } ) != v.end())
if (std::any_of(v.begin(), v.end(), [] (int i) { return i < 3 && i > 1 } ))

string str="hello world , hi";
reverse(str.begin(),str.end());//str结果为 ih , dlrow olleh
vector<int> v = {5,4,3,2,1};
reverse(v.begin(),v.end());//容器v的值变为1,2,3,4,5

cout << max({ 54,16,48,5 }) << endl;   //输出54

std::copy(start, end, container);
int arr[] = {1,2,3,4,5,6,7,8,9,10};
int newArr[12] = {0};
copy(arr,arr+10,newArr); 

//四舍五入round//向上取整ceil//向下取整floor
int a = round(11.5); //a = 12
int b = round(-11.5); //b = -12
auto c = double(11)/2; //c = 5.5
auto d = round(double(11)/2); // d = 6

//借助 advance() 函数将 it 迭代器前进 2 个位置 
advance(it, 2);
new_iterator = prev(iterator，n)//-n

//获取 [first,last) 范围内包含元素的个数 
cout << "distance() = " << distance(mylist.begin(), mylist.end());

int n=stoi("1.234");
cout<<n;
//此时会输出1。
std::string pi = "pi is " + std::to_string(3.1415926)；
//输出： pi is 3.1415926

int hammingDistance(int x, int y) {
        return __builtin_popcount(x ^ y);//统计二进制下“1”的个数
    }

vector

//eg: double Distance(vector<int>&a, vector<int>&b) 其中的"&"绝对不能少
vector<int>v;
a=10;
v.push_back(a);
vector<vector<int>>t;// 二维数组
t[0].size();// 第一行的列数
cout<<v[0]<<endl;// 通过下标访问
// 通过迭代器遍历
vector<int>::iterator it;
for(it=v.begin();it!=v.end();it++)
    cout<<*it<<endl;
v.insert(v.begin()+i,a);// 在第i+1个元素前面插入a;
v.erase(v.begin()+2);// 删除第3个元素
int len=v.size();
v.clear();

string

string str ;
string str2 =“123”;
//在str后面追加一个str2
str.append(str2);   //输出123
//在后面追加上str2中从第二个元素开始的连续一个元素
str.strappend(str2,1,1); //1232
//在str后面追加上abc
str.append(“abc”);  //1232abc
//在str后面追加上字符串123456中的前六个元素 
str.append(“123456”, 6);  
//在str后面追加5个m 
str.append(5,‘m’);  
//使用迭代器给str追加上str2的元素
str.append(str2.begin(),str2.end());  

string str = "he is@ a@ good boy";
str = str.replace(str.find("a"), 2, "#");  //从第一个a位置开始的两个字符替换成#
cout << str << endl; //he is@ # good boy

string& replace (size_t pos, size_t len, const string& str, size_t subpos, size_t sublen);
string str = "he is@ a@ good boy";
string substr = "12345";
str = str.replace(0,5, substr, substr.find("1"), 4); //用substr的指定字符串替换str指定字符串
cout << str << endl; //1234@ a@ good boy

string& replace (size_t pos, size_t len, size_t n, char c); 
char  ch = '#';
str = str.replace(0, 6, 3, ch);   //用重复 3 次的 str1 字符替换的替换从位置 0~6 的字符串
cout << str << endl; //### a@ good boy

char  ch = '#';
str = str.replace(str.begin(), str.begin() + 6, 3, ch);   //用重复3次的str1字符替换的替换从指定迭代器位置的内容
cout << str << endl; //### a@ good boy

tolower();toupper();
string str;  cin>>str;
transform(str.begin(), str.end(), str.begin(), ::toupper);//转为大写
transform(str.begin(), str.end(), str.begin(), ::tolower);//转为小写

isalpha(str[i]);islower(str[i]);isupper(str[i]);

map与set

mapStudent.insert(pair<int, string>(1, "student_one"));
.first;.second
.find();//返回迭代器，找不到返回.end()
.count();//返回0或1
 m.erase(m.begin(),m.end());//删除的是一个前闭后开的集合

set<int> st;
st.insert(i);
set<int>::iterator it = st.find(2); //在 set 中查找2，返回其迭代器。
st.erase(st.find(200)); //利用 find() 函数找到200，然后用 erase 删除它。o1
st.erase(200); //用 erase 删除200。ologn
st.erase(st.find(300),st.end());
.size();.clear();

multiset<int> s;//允许元素重复
c.lower_bound(val) 返回 val 的第一个可安插位置，也就是“元素值 >= val ”的第一个元素位置
c.upper_bound(val) 返回 val 的最后一个可安插位置，也就是“元素值 > val ”的第一个元素位置
c.equal_range(val) 返回 val 可被安插的第一个位置和最后一个位置，也就是“元素值 == val ”的元素区间。将 lower_bound() 和 upper_bound() 的返回值做成一个 pair 返回。如果 lower_bound() 或“ equal_range() 的 first 值”等于“ equal_range() 的 second 值”或 upper_bound()，则此 set 或 multiset 内不存在同值元素。

stack、queue、bitset、deque、priority_queue

int main(){
	stack<int> st;
	for(int i=1;i<=5;i++){
		st.push(i);		//push(i)将i压入栈 
	}
	printf("%d\n",st.top()); 	//top()取栈顶元素 
	return 0;
}

queue <string> q;
q.push("first");
q.push("second");
cout<<q.front()<<endl;
q.pop();
cout<<q.front()<<q.back()<<endl;

deque<int> mydeque = {2, 3};//双端队列
cout<< "添加元素前mydeque.size() = "<< mydeque.size()<<endl;
// 在deque头部插入一个元素5
mydeque.push_front(5);
// 在deque尾部插入一个元素5
mydeque.push_back(1);
cout<< "添加元素后mydeque.size() = "<< mydeque.size()<<endl;
int num2 = mydeque.at(2); cout << "\nmydeque中索引为2的元素为：" << num2;
mydeque.assign(3, 2);//assign的作用就是用新的元素替换deque中旧的元素

bitset< n > s;  //表示一个n位的二进制数，<>中填写位数；
s[k];//表示s的第k位，即可取值也可赋值，编号从0开始；
s.count() //返回二进制串中有多少个1；
//若s所有位都为0，则s.any()返回false，s.none()返回true；  
//若s至少有一位为1，则s.any()返回true，s.none()返回false；
s.set();//把s所有位变为1；
s.set(k,v);//把s的第k位改为v,即s[k]=v；
s.reset();//把s的所有位变为0.
s.reset(k);//把s的第k位改为0,即s[k]=0；
s.flip();//把s所有位取反.即s=~s；
s.flip(k);//把s的第k位取反，即s[k]^=1；

//对于基础类型 默认是大顶堆 
priority_queue<int> a; //等同于 priority_queue<int, vector<int>, less<int> > a;
priority_queue<int, vector<int>, greater<int> > c; //这样就是小顶堆 priority_queue<string> b;
- top 访问队头元素
- empty 队列是否为空
- size 返回队列内元素个数
- push 插入元素到队尾 (并排序)
- emplace 原地构造一个元素并插入队列
- pop 弹出队头元素
- swap 交换内容
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};
priority_queue<tmp1> d;

常用模板

C无序排列组合，结果取模d

typedef long long ll;
const int d = 1e9 + 7;

ll fastpow(ll a, ll k)
{
	ll res = 1;
	while (k) {
		if (k & 1)res = res * a % d;
		a = a * a % d;
		k >>= 1;
	}
	return res;
}
ll C(ll b, ll a)
{
	ll res = 1;
	if (a > b || b == 0)return 0;
	if (a == b || a == 0)return 1;
	for (int i = 1; i <= a; i++) {
		res = (((res % d) * ((b - i + 1) % d)) % d * fastpow(i, d - 2)) % d;
	}
	return res;
}

网络流（ISAP）

#include <bits/stdc++.h>

using namespace std;

const int N = 100;          //点数，从1开始编号
const int M = 100000;       //边数
const int inf = 1000000000; //无穷大
struct E
{
    int t, f;
    E *nxt, *pair;
} * g[N], *d[N], pool[M * 2], *cur = pool;

int n, m, i, S, T, h[N], gap[N], maxflow;

void add(int s, int t, int f)
{ //添加s->t的一条边，容量为f
    E *p = cur++;
    p->t = t;
    p->f = f;
    p->nxt = g[s];
    g[s] = p;
    p = cur++;
    p->t = s;
    p->f = 0;
    p->nxt = g[t];
    g[t] = p;
    g[s]->pair = g[t];
    g[t]->pair = g[s];
}

int sap(int v, int flow)
{
    if (v == T)
        return flow;
    int rec = 0;
    for (E *p = d[v]; p; p = p->nxt)
        if (h[v] == h[p->t] + 1 && p->f)
        {
            int ret = sap(p->t, min(flow - rec, p->f));
            p->f -= ret;
            p->pair->f += ret;
            d[v] = p;
            if ((rec += ret) == flow)
                return flow;
        }
    if (!(--gap[h[v]]))
        h[S] = T;
    gap[++h[v]]++;
    d[v] = g[v];
    return rec;
}

void solve(int id)
{
    //S = n + 1; //源点
    //T = S + 1; //汇点
    S=1;
    T=n;
    for (cur = pool, i = 1; i <= T; i++)
        g[i] = d[i] = NULL, h[i] = gap[i] = 0; //初始化

    //请在这里连边
    for (int j = 1; j <= m; j++)
    {
        int s, t, f;
        cin >> s >> t >> f;
        add(s, t, f);
    }

    for (gap[maxflow = 0] = T, i = 1; i <= T; i++)
        d[i] = g[i];
    while (h[S] < T)
        maxflow += sap(S, inf);
    cout << maxflow <<"\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt;
    cin >> tt;
    for (int i = 1; i <= tt; i++)
    {
        cin >> n >> m;
        solve(i);
    }
    return 0;
}

求Mex

ll mmex(ll v[])
{
    bitset<200010> vis;
    vis.set();
    for (int i = 1; i <= n; i++)
        if (v[i] <= n)
            vis[v[i]] = 0;
    return vis._Find_first();
}

二维前缀和

const int N = 1010;
int a[N][N],s[N][N];
int n, m, q;
int main()
{
    cin>>n>>m>>q;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    
    for(int i = 0; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
    while(q --)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

题目

【模板】二维差分

题目描述

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1，y1，x2，y2，c，其中 (x1, y1) 和 (x2, y2) 表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上 c。 请你将进行完所有操作后的矩阵输出。

输入

第一行包含整数 n，m，q。 接下来 n 行，每行包含 m 个整数，表示整数矩阵。 接下来 q 行，每行包含 5 个整数 x1，y1，x2，y2，c，表示一个操作。

输出

共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

样例输入
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
样例输出
2 3 4 1
4 3 4 1
2 2 2 2
数据范围

1 ≤ n, m ≤ 1000,
1 ≤ q ≤ 100000,
1 ≤ x1 ≤ x2 ≤ n,
1 ≤ y1 ≤ y2 ≤ m,
−1000 ≤ c ≤ 1000,
−1000 ≤ 矩阵内元素的值 ≤ 1000

code
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e3+6;
const int MAXM = 1e3+6;
int a[MAXN][MAXM] = {};
int diff[MAXN][MAXM] = {};
 
int main() {
    int n,m,q;
    scanf("%d%d%d", &n, &m, &q);
 
    int i, j;
    for (i=1; i<=n; i++) {
        for (j=1; j<=m; j++) {
            scanf("%d", &a[i][j]);
            diff[i][j] = a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
        }
    }
 
    for (i=0; i<q; i++) {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        diff[x1][y1] += c;
        diff[x1][y2+1] -=c;
        diff[x2+1][y1] -=c;
        diff[x2+1][y2+1] += c;
    }
 
    for (i=1; i<=n; i++) {
        for (j=1; j<=m; j++) {
            diff[i][j] += diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1];
            printf("%d ", diff[i][j]);
        }
        printf("\n");
    }
 
    return 0;
}

【模板】树状数组 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  • 将某一个数加上 $x$

  • 求出某区间每一个数的和

输入格式

第一行包含两个正整数 $n,m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

  • 1 x k 含义：将第 $x$ 个数加上 $k$

  • 2 x y 含义：输出区间 $[x,y]$ 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 $2$ 的结果。

样例 #1
样例输入 #1
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
样例输出 #1
14
16
提示

【数据范围】

对于 $30%$ 的数据，$1 \le n \le 8$，$1\le m \le 10$；
对于 $70%$ 的数据，$1\le n,m \le 10^4$；
对于 $100%$ 的数据，$1\le n,m \le 5\times 10^5$。

数据保证对于任意时刻，$a$ 的任意子区间（包括长度为 $1$ 和 $n$ 的子区间）和均在 $[-2^{31}, 2^{31})$ 范围内。

解决代码
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=2e6+10;
const int NN=5e5+10;
ll n,m,f[N];
ll a[NN];
void build(ll k,ll l,ll r)
{
	if(l==r){
		f[k]=a[l];
		return;
	}
	ll m=(l+r)>>1;
	build(k+k,l,m);
	build(k+k+1,m+1,r);
	f[k]=f[k+k]+f[k+k+1];
	return;
}
void add(ll k,ll l,ll r,ll x,ll t)
{
	f[k]+=t;
	if(l==r){
		return;
	}
	ll m=(l+r)>>1;
	if(x<=m){
		add(k+k,l,m,x,t);
	}
	else{
		add(k+k+1,m+1,r,x,t);
	}
	return;
}
ll cal(ll k,ll l,ll r,ll x,ll y){
	if(l==x&&r==y){
		return f[k];
	}
	ll m=(l+r)>>1;
	if(y<=m){
		return cal(k+k,l,m,x,y);
	}
	else if(x>m){
		return cal(k+k+1,m+1,r,x,y);
	}
	else return cal(k+k,l,m,x,m)+cal(k+k+1,m+1,r,m+1,y);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(ll i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(ll i=1;i<=m;i++){
		ll op;
		cin>>op;
		if(op==1){
			ll x,k;
			cin>>x>>k;
			add(1,1,n,x,k);
		}
		else{
			ll x,y;
			cin>>x>>y;
			cout<<cal(1,1,n,x,y)<<"\n";
		}
	}
	return 0;
}

【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 $k$。
  2. 求出某区间每一个数的和。
输入格式

第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 $[x, y]$ 内每个数加上 $k$。
  2. 2 x y：输出区间 $[x, y]$ 内每个数的和。
输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1
样例输入 #1
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
样例输出 #1
11
8
20
提示

对于 $30%$ 的数据：$n \le 8$，$m \le 10$。
对于 $70%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。
对于 $100%$ 的数据：$1 \le n, m \le {10}^5$。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。

解决代码1
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=4e5+10;
const int NN=1e5+10;
ll n,m,f[N],d[N];
ll a[NN];
void build(ll k,ll l,ll r)
{
	d[k]=0;
	if(l==r){
		f[k]=a[l];
		return;
	}
	ll m=(l+r)>>1;
	build(k+k,l,m);
	build(k+k+1,m+1,r);
	f[k]=f[k+k]+f[k+k+1];
	return;
}
void add(ll k,ll l,ll r,ll x,ll y,ll t)
{
	if(l==x&&r==y){
		d[k]+=t;
		return;
	}
	f[k]+=(y-x+1)*t;
	ll m=(l+r)>>1;
	if(y<=m){
		add(k+k,l,m,x,y,t);
	}
	else if(x>=m+1){
		add(k+k+1,m+1,r,x,y,t);
	}
	else{
		add(k+k,l,m,x,m,t);
		add(k+k+1,m+1,r,m+1,y,t);
	}
	return;
}
ll cal(ll k,ll l,ll r,ll x,ll y,ll p){
	p+=d[k];
	if(l==x&&r==y){
		return f[k]+(r-l+1)*p;
	}
	ll m=(l+r)>>1;
	if(y<=m){
		return cal(k+k,l,m,x,y,p);
	}
	else if(x>m){
		return cal(k+k+1,m+1,r,x,y,p);
	}
	else return cal(k+k,l,m,x,m,p)+cal(k+k+1,m+1,r,m+1,y,p);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(ll i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(ll i=1;i<=m;i++){
		ll op;
		cin>>op;
		if(op==1){
			ll x,y,k;
			cin>>x>>y>>k;
			add(1,1,n,x,y,k);
		}
		else{
			ll x,y;
			cin>>x>>y;
			cout<<cal(1,1,n,x,y,0)<<"\n";
		}
	}
	return 0;
}
解决代码2 标记下放
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e5+10;
const int NN=4e5+10;

ll n,m;
ll a[N];
ll f[NN],d[NN];

void build(ll k,ll l,ll r) {
	d[k]=0;
	if(l==r) {
		f[k]=a[l];
		return;
	}
	ll m=(l+r)>>1;
	build(k+k,l,m);
	build(k+k+1,m+1,r);
	f[k]=f[k+k]+f[k+k+1];
	return;
}

void insert(ll k,ll l,ll r,ll x,ll y,ll t) {
	if(l==x&&r==y) {
		d[k]+=t;
		return;
	}
	if(d[k])d[k+k]+=d[k],d[k+k+1]+=d[k],d[k]=0;
	ll m=(l+r)>>1;
	if(y<=m)insert(k+k,l,m,x,y,t);
	else if(x>m)insert(k+k+1,m+1,r,x,y,t);
	else insert(k+k,l,m,x,m,t),insert(k+k+1,m+1,r,m+1,y,t);
	f[k]=f[k+k]+f[k+k+1]+d[k+k]*(m-l+1)+d[k+k+1]*(r-m);
	return;
}

ll cal(ll k,ll l,ll r,ll x,ll y) {
	if(l==x&&r==y)return f[k]+(r-l+1)*d[k];
	if(d[k])d[k+k]+=d[k],d[k+k+1]+=d[k],d[k]=0;
	ll res;
	ll m=(l+r)>>1;
	if(y<=m)res=cal(k+k,l,m,x,y);
	else if(x>m)res=cal(k+k+1,m+1,r,x,y);
	else res=cal(k+k,l,m,x,m)+cal(k+k+1,m+1,r,m+1,y);
	f[k]=f[k+k]+f[k+k+1]+d[k+k]*(m-l+1)+d[k+k+1]*(r-m);
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	build(1,1,n);
	for(int i=1; i<=m; i++) {
		ll op;
		cin>>op;
		if(op==1) {
			ll x,y,k;
			cin>>x>>y>>k;
			insert(1,1,n,x,y,k);
		} else {
			ll x,y;
			cin>>x>>y;
			cout<<cal(1,1,n,x,y)<<endl;
		}
	}
	return 0;
}

记录

Note

  • 202209-2 背包问题，将求（超过限制的最少）转化为（小于限制的最多）
  • 202212-2 暴力搜索
  • 202303-2 二分或优化cost数组（结构体排序，iterator用法）
  • 202206-1 sqrt，pow返回的是double，memset使用0,-1,0x3f,double不能用==
  • 202206-2 vector<pair,pair>a;a.push_back({x,y});a.first;a.second

Code

20220601

#include<bits/stdc++.h>

using namespace std;

double a[1010];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	double sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	double t=sum/n;
	double d=0;
	for(int i=1;i<=n;i++){
		d+=(a[i]-t)*(a[i]-t);
	}
	d/=n;
	for(int i=1;i<=n;i++){
		cout<<(a[i]-t)/sqrt(d)<<endl;
	}
	return 0;
}

20220602

#include<bits/stdc++.h>

using namespace std;

vector<pair<int,int>>a;
int mp[55][55];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	memset(mp,0,sizeof(mp));
	int n,l,s;
	cin>>n>>l>>s;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		a.push_back({x,y});
	}
	int tcnt=0;
	for(int i=s;i>=0;i--){
		for(int j=0;j<=s;j++){
			cin>>mp[i][j];
			if(mp[i][j])tcnt++;
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		if(a[i].first+s>l||a[i].second+s>l)
			continue;
		int flag=1;
		int xx=a[i].first;
		int yy=a[i].second;
		int cnt=0;
		for(int j=0;j<n;j++){
			if(a[j].first>=xx&&a[j].first<=xx+s&&a[j].second>=yy&&a[j].second<=yy+s){
				if(mp[a[j].first-xx][a[j].second-yy]==0){
					flag=0;
					break;
				}
				else cnt++;
			}	
			else continue;
		}
		if(flag==1&&cnt==tcnt)ans++;
	}
	cout<<ans<<endl;
	return 0;
}

20220902

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=3e5+10;
int a[40];
int dp[40][N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n,x;
	cin>>n>>x;
	memset(dp,0,sizeof(dp));
	int sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	int v=sum-x;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=v;j++){
			if(j-a[i]>=0){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);
			}
			else dp[i][j]=dp[i-1][j];
		}
	}
	cout<<sum-dp[n][v]<<endl;
	return 0;
}

202303-2 解法1：二分

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Node{
	int t;
	int c;
};
const int N=1e5+10;
Node a[N];
int n,m,k;

int check(int d){
	if(d<k)return 0;
	int nn=n,mm=m,kk=k;
	for(int i=1;i<=nn;i++){
		if(a[i].t>d){
			int cost=(a[i].t-d)*a[i].c;
			if(mm-cost<0)
				return 0;
			else
				mm-=cost;
		}
	}
	return 1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie();cout.tie(0);
	cin>>n>>m>>k;
	int mx=0;
	for(int i=1;i<=n;i++){
		cin>>a[i].t>>a[i].c;
		mx=max(mx,a[i].t);
	}
	int l=k,r=mx;
	int ans=mx;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			ans=min(ans,mid);
			r=mid-1;
		}
		else l=mid+1;
	}
	cout<<ans<<endl;
	return 0;
}

202303-2 解法2：优化cost数组

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=1e5+10;
ll n,m,k;
ll cost[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	memset(cost,0,sizeof(cost));
	cin>>n>>m>>k;
	ll mx=0;
	for(ll i=1;i<=n;i++){
		ll t,c;
		cin>>t>>c;
		mx=max(mx,t);
		if(t>k){
			cost[t]+=c;
		}
	}
	ll ans=mx;
	for(ll i=mx;i>=k;i--){
		ans=i;
		if(m-cost[i]>=0){
			m-=cost[i];
			cost[i-1]+=cost[i];
		}
		else break;
	}
	cout<<ans<<endl;
	return 0;
}

202212-1

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	double i;
	cin>>n>>i;
	double ans=0;
	for(int j=0;j<=n;j++){
		double x;
		cin>>x;
		ans+=x*pow(1+i,-j);
	}
	cout<<ans<<endl;
	return 0;
}

202212-2 暴力搜索

#include<bits/stdc++.h>

using namespace std;

const int N=110;
int p[N];
int t[N];
int pp[N];
int st[N];
int mp[N][N];
int n,m;

int cal_st(int id)
{
	int st=1;
	id=p[id];
	while(1){
		st+=t[id];
		if(p[id]==0)break;
		id=p[id];
	}
	return st;
}
int ss(int id){
	int sum=t[id];
	int mx=0;
	for(int i=id+1;i<=m;i++){
		if(mp[id][i])
			mx=max(mx,ss(i));
	}
	return sum+mx;
}
int cal_ed(int id){
	return n-ss(id)+1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	memset(mp,0,sizeof(mp));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>p[i];
		if(p[i])mp[p[i]][i]=1;
	}
	for(int i=1;i<=m;i++){
		cin>>t[i];
	}
	int mx=0;
	for(int i=1;i<=m;i++){
		st[i]=cal_st(i);
		mx=max(mx,st[i]+t[i]-1);
		cout<<st[i]<<" ";
	}
	cout<<"\n";
	if(mx<=n){
		for(int i=1;i<=m;i++){
			cout<<cal_ed(i)<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

Note

  • 补题（上周六的debug杯）
  • 1005 选数游戏：大意：对于一个由n个整数构成的数列a1​,a2​,...,an，​按序取出相邻下标小于等于k的元素，目标是输出子序列所有元素的最大和。
  • 思路：dp，状态转换方程：sum[i]=max(sum[i],max(sum[i-k],sum[i-k+1],...sum[i-1])+a[i])
  • 1003 给你一张有n个顶点和m条边的无向图， 你要判断它是不是一棵树。
  • 思路：邻接矩阵，先用边点先判断，再使用bfs或dfs查找是否联通，注意需要将vis和a数组更新（or 清零）。

Code

// 1005
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll sum[1010];
ll a[1010];
void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = a[i];
    }
    ll ans = 0;
    for (int i = 2; i <= n; i++)
        for (int j = max(0, i - k); j < i; j++)
        {
            sum[i] = max(sum[i], sum[j] + a[i]);
            ans = max(ans, sum[i]);
        }
    cout << ans << endl;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt;
    cin >> tt;
    while (tt--)
        solve();
    return 0;
}
// 1003
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int a[2010][2010];
int vis[2010];
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        vis[i] = 0;
        for (int j = 1; j <= n; j++)
            a[i][j] = a[j][i] = 0;
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        a[u][v] = a[v][u] = 1;
    }
    if (m != n - 1)
    {
        cout << "no\n";
        return;
    }
    queue<int> q({1});
    vis[1] = 1;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        for (int i = 1; i <= n; i++)
        {
            if (vis[i] || a[t][i] == 0)
                continue;
            q.push(i);
            vis[i] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            cout << "no\n";
            return;
        }
    }
    cout << "yes\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt;
    cin >> tt;
    while (tt--)
        solve();
    return 0;
}