lzx's blog T1
if & else
std
/*
Author:lzx
Blog:https://blog.lzx9.com/
Email:lzx@czoier.top
QQ:2210631299
*/
#include<bits/stdc++.h>
using namespace std;
int x,y;
char o;
int main()
{
cin>>x>>o>>y;
if(x+y>=100 || (x/10+y/10)!=(x+y)/10 || o!='+') puts("PR!");
else cout<<x+y<<"\n";
return 0;
}T2
差分
std
/*
Author:lzx
Blog:https://blog.lzx9.com/
Email:lzx@czoier.top
QQ:2210631299
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+10,MX=1e7;
int m,k,s[MAXN];
int main()
{
cin>>m>>k;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
s[a]++;
s[b+1]--;
}
for(int i=1;i<=MX;i++)
{
s[i]+=s[i-1];
}
while(k--)
{
int x;
cin>>x;
cout<<s[x]<<"\n";
}
return 0;
}T3
处理每个点单个长条可覆盖到的最远方格 $a_i$
$$ \color{red}30 pts $$
从每个方格开始，每次用一个长条，重复 $k$ 次
$$ \color{green}100pts $$
依旧从每个方格开始，求用 $k$ 个长条覆盖的最远方格
我们对
求用 $k$ 个长条覆盖的最远方格
的步骤进行优化，比如 $k=5$ 我们可以先用 $2^2$ 个长条，再在用 $2^2$ 个长条覆盖到点最远方格的基础上用 $2^0$ 个长条覆盖，也可以得到
用 $k$ 个长条覆盖的最远方格
我们用 st[i][j] 表示从 $i$ 开始，用 $2^j$ 个长条可以覆盖到的最远方格。
易得：st[i][j]=st[st[i][j-1]][j-1]
边界：st[i][0]=a[i]
std
/*
Author:lzx
Blog:https://blog.lzx9.com/
Email:lzx@czoier.top
QQ:2210631299
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
int n,k,a[MAXN],lg2[MAXN],st[MAXN][32];
int ans;
void STinit()
{
for(int i=1;i<=lg2[n];i++)
{
for(int j=1;j<=n+1;j++)
{
st[j][i]=n;
}
}
lg2[1]=0;
for(int i=2;i<=n;i++)
{
lg2[i]=lg2[i>>1]+1;
}
for(int i=1;i<=n;i++)
{
st[i][0]=a[i];
}
for(int i=1;i<=lg2[n];i++)
{
for(int j=1;j<=n;j++)
{
st[j][i]=st[st[j][i-1]][i-1];
}
}
}
int query(int x)
{
int cnt=k,xx=x;
while(cnt)
{
x=st[x][lg2[cnt]];
cnt&=((1<<lg2[cnt])-1);
}
return x-xx+1;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
a[i]=i;
}
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[max(1,i-x)]=max(a[max(1,i-x)],min(n,i+x));
}
for(int i=1;i<=n;i++)
{
a[i]=max(a[i],a[i-1]);
}
STinit();
for(int i=1;i<=n;i++)
{
ans=max(ans,query(i));
}
cout<<ans<<"\n";
return 0;
}T4
我们可以把这些优先关系看成一个图。比如 $2$ 任务处理完后才能处理 $1$ 任务，就连一条 $2$ 到 $1$ 的有向边。
比如我们构造了如下的一个图：
在此图中，我们观察到 $4,5$ 节点没有前驱任务（即入度为 $0$），这些任务可以优先处理。
于是图就会变成这样：
在这张图中，没有任何一个点可以处理。
因此，我们只要每次把入读为 $0$ 的点移除，知道没有点入读为 $0$。
在这里，我们可以把入读为 $0$ 的数塞入 queue 中，将时间复杂读将为 $\mathcal{O}(n)$。
std
#include<bits/stdc++.h>
using namespace std;
int d[300100];
queue<int> q;
vector<int> a[300100];
bool h[300100];
int main()
{
int T;
cin>>T;
while (T--)
{
memset(h,0,sizeof h);
while (!q.empty())
q.pop();
int n;
cin>>n;
for (int i=1;i<=n;i++)
a[i].clear();
for (int i=1;i<=n;i++)
{
cin>>d[i];
for (int j=1;j<=d[i];j++)
{
int x;
cin>>x;
a[x].push_back(i);
}
}
for (int i=1;i<=n;i++)
if (d[i]==0) q.push(i);
while (!q.empty())
{
int x=q.front();
q.pop();
h[x]=1;
for (auto i:a[x])
{
d[i]--;
if (d[i]==0) q.push(i);
}
}
int ans=0;
for (int i=1;i<=n;i++)
if (!h[i]) ans++;
cout<<ans<<endl;
for (int i=1;i<=n;i++)
if (!h[i]) cout<<i<<' ';
if (ans!=0) cout<<endl;
}
return 0;
}T5
std
T6
改编自 CF734E
使用树的直径求解
std
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector <int> color;
vector < vector <int> > g;
vector <char> used;
vector <int> comp;
int n1;
vector < vector <int> > g1;
vector <int> dp;
int ans = 0;
void dfs1(int v, int col, int cmp)
{
if (used[v]) return;
if (color[v] != col) return;
used[v] = true;
comp[v] = cmp;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
dfs1(to, col, cmp);
}
}
void dfs2(int v, int p = -1)
{
int mx1 = 0, mx2 = 0;
for (int i = 0; i < g1[v].size(); i++)
{
int to = g1[v][i];
if (to == p) continue;
dfs2(to, v);
int val = dp[to] + 1;
mx2 = max(mx2, val);
if (mx1 < mx2) swap(mx1, mx2);
}
dp[v] = mx1;
ans = max(ans, mx1 + mx2);
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> n;
color.resize(n);
g.resize(n);
comp.resize(n);
used.assign(n, false);
string panrui;
cin>>panrui;
for (int i = 0; i < n; i++)
{
if(panrui[i]=='G')
{
color[i]=1;
}
else color[i]=0;
}
for (int i = 1; i < n; i++)
{
int a, b; cin >> a >> b; a--, b--;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 0; i < n; i++)
if (!used[i])
dfs1(i, color[i], n1++);
g1.resize(n1);
dp.resize(n1);
for (int i = 0; i < n; i++)
for (int j = 0; j < g[i].size(); j++)
{
int to = g[i][j];
if (comp[i] != comp[to])
g1[comp[i]].push_back(comp[to]);
}
dfs2(0);
cout << (ans + 1) / 2 << endl;
return 0;
}