一些有趣的题
codesonic
2018-08-11 23:43:37
个人觉得有趣而已qwq,不按难度排序
[牧场散步](https://www.luogu.org/problemnew/show/P2912)
在bzoj似乎是权限题
不过没关系
这是usaco资格赛题
可以树上前缀和+lca做
然而发现可以floyd剪枝，在第二层剪掉从i无法到k的
这是一棵树所以剪枝很优，均摊似乎可以优化到$O(n^2*2)$
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
const int INF=(1<<30);
int dis[maxn][maxn];
int main() {
int n,q;
memset(dis,0x3f,sizeof(dis));
scanf("%d%d",&n,&q);
for(int i=1;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
dis[u][v]=dis[v][u]=w;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
if(dis[i][k]>(1<<29))
continue;
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
while(q--){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",dis[x][y]);
}
return 0;
}
```
P1338 末日的传说
神题，没看题解真的推不出
直接贴题解了
>我们知道一个长度为n的排列最多有(n-1)*n/2个逆序对，也知道一个排列的逆序对数越多，排列字典序越大。
>所以如果当前m不比当前的(n-2)*(n-1)/2（也就是减少一个数之后的最多的逆序对数）大，
>就可以直接把当前的最小数放在最前面，这肯定是最优的。
>反之，则考虑最小数的放置位置。
>假设当前排列长为n，最小数为a，则a有n种放法，放在从左到右第i个位置时会生成i-1个逆序对
>（因为它左边有i-1个比他大）。
>因为m大于n-1长度排列最多所能产生的逆序数，所以a不可能放在最前面，否则不满足条件。
>怎么办呢？想到之前说的逆序对越多字典序越大，我们就必须让剩下的数能构成的逆序对数尽量小，所以a要放到最后，这样m减少的最多。
>放完了a，问题就变成了n-1和m-(a的贡献)的子问题，递归求解即可。时间复杂度O(n)。
```cpp
#include<cstdio>
using namespace std;
#define int long long
int n,m,a[100010];
int head,tail;
main()
{
scanf("%lld%lld",&n,&m);
for(register int i=1,head=1,tail=n;i<=n;i++){
int tmp=((n-i)*(n-i-1))>>1;
if(m<=tmp)
a[head++]=i;
else a[tail--]=i,m-=tail-head+1;
}
for(register int i=1;i<=n;i++)
printf("%lld ",a[i]);
return 0;
}
```
[P1131](https://www.luogu.org/problemnew/show/P1131)
贪心题，贪心的策略很有趣
dfs，dfs到每个节点，记录每个节点的子树到达时态同步所需的最小时间
然后用每个儿子更新这个时间，详见第一篇题解
为什么这样做是对的。。。？因为每个节点同步，上面的节点才能同步，满足了个DP的关系
其实本质好像是dp吧
我果然还是菜啊
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
inline int read() {
int res=0,fh=1;
char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
if(ch=='-')fh=-1,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
return fh*res;
}
typedef long long ll;
const int maxn=500010;
int n,m,rt,val[maxn];
ll ans;
struct node{
int to,w,nxt;
}t[maxn<<1]; int head[maxn],tot=0;
inline void addedge(int u,int v,int w){
t[++tot].to=v;
t[tot].w=w;
t[tot].nxt=head[u];
head[u]=tot;
}
void dfs(int u,int fa){
int cnt=0;
for(int i=head[u];i;i=t[i].nxt){
int to=t[i].to;
if(to!=fa){
dfs(to,u);
if(val[to]+t[i].w>val[u]){
ans+=(val[to]+t[i].w-val[u])*(cnt++);
val[u]=val[to]+t[i].w;
}
else ans+=val[u]-val[to]-t[i].w,++cnt;
}
}
}
int main(){
n=read(),rt=read();
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
addedge(u,v,w);
addedge(v,u,w);
}
dfs(rt,0);
printf("%lld",ans);
return 0;
}
```
[P4185](https://www.luogu.org/problemnew/show/P4185)
将询问离线，按照询问的k排序
然后把边也排序，由小到大慢慢连边，顺便处理k值小于当前边权的询问
这道题的妙处在于`FJ决定将任意一对视频的相关性定义为沿此路径的任何连接的最小相关性`
这道题可以扩展出来的思想就是询问的和边权的最值相关，大概都可以用这种方法处理吧。。。
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=100010;
int n,q;
int fa[maxn],ans[maxn],size[maxn];
struct edge{
int x,y,w;
}G[maxn];
inline bool cmp(edge a,edge b){
return a.w>b.w;
}
struct que{
int k,v,id;
}a[maxn];
inline bool cmp1(que a,que b){
return a.k>b.k;
}
inline void init(){
for(int i=1;i<=n;i++)
fa[i]=i,size[i]=1;
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<n;i++)
scanf("%d%d%d",&G[i].x,&G[i].y,&G[i].w);
sort(G+1,G+1+n,cmp);
for(int i=1;i<=q;i++){
scanf("%d%d",&a[i].k,&a[i].v);
a[i].id=i;
}
sort(a+1,a+1+q,cmp1);
init();
int tot=1;
for(int i=1;i<=q;i++){
while(tot<n&&G[tot].w>=a[i].k){
int x=find(G[tot].x),y=find(G[tot].y);
if(x^y)
fa[x]=y,size[y]+=size[x];
tot++;
}
ans[a[i].id]=size[find(a[i].v)]-1;
}
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
return 0;
}
```
[P1282 多米诺骨牌](https://www.luogu.org/problemnew/show/P1282)
好题，可以建立一个类似于背包的模型
因为急着去睡觉，所以抄个题解原话进来
> 我们先把骨牌翻转，调整至点数大的在上面
>这样，我们就能保证上方的点数一定比下方大，并且保证每翻转一 次，都能使上下的点数之差变小，而变小的点数，就是上下点数之差乘以2。
>把改变的点数看成物品的体积，初始上下方的点数之差看做背包体积，不难看出背包问题的模型。
>那么物品的重量是什么呢？
>因为我们一开始就把点数大的放在了上面，而每放一次，翻转次数就+1。考虑：要是我后来后悔了，我发现不翻这个骨牌更好怎么办？那我会把它翻回来，那么相当于没有翻这个骨牌。
>因此，一开始翻过的骨牌重量就是-1，未翻过的骨牌重量就是1（重量等价于翻转次数）
>当然，上下相同的骨牌就是体积为0，重量为0的物品，因为他们无论怎么翻，都不会对上下点数差造成影响。
>至此，背包的模型就出来了。这个问题被简化成：有n个物品，给出每个物品的体积v[i],他们的重量是1或-1。背包的重量为base，体积为tot，现在请把这n个物品放到背包里去，总体积不能超过tot，体积最大的情况下使得物品重量之和最小。
>其中，dp[i][j]表示前i件物品能装到体积为j的最小重量
>vs[i][j]表示前i件物品能否装到j体积
这题的模型的建立还是挺好的，可惜背包不是唯一解法
可能可以作为以后造题的思路吧
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
inline int read() {
int res=0,fh=1;
char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
if(ch=='-')fh=-1,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
return fh*res;
}
inline int Min(int a,int b){
return a<b?a:b;
}
inline void Swap(int &a,int &b){
b^=a^=b^=a;
}
const int maxn=1010;
int n,sum=0,tot=0,f[maxn][6010],v[maxn],w[maxn];
bool flag[maxn][6010];
int main()
{
n=read();
for(int i=1;i<=n;i++){
int x=read(),y=read();
int flag=1;
if(y>x) Swap(x,y),flag=-1;
v[i]=(x-y)<<1;
w[i]=flag;
tot+=x-y;
if(flag==-1) sum++;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=tot;j++){
f[i][j]=f[i-1][j];
flag[i][j]=flag[i-1][j];
if(flag[i-1][j-v[i]]||!(j^v[i])){
if(!flag[i][j])
f[i][j]=f[i-1][j-v[i]]+w[i],flag[i][j]=1;
else f[i][j]=Min(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
}
for(int i=tot;i;i--)
if(flag[n][i]) return printf("%d\n",sum+f[n][i]),0;
}
```
[P3521P4187 \[USACO18JAN\]Stamp Painting(https://www.luogu.org/problemnew/show/P3521)
DP，一个好像很经典的DP方式
题意是给n,m,k，有n个格子，用m种颜色覆盖，每次只能覆盖k个连续格子，，问一共有多少种最终状态，因为一个格子可以被重复覆盖，所以其实是求至少有一个长度为k的相同颜色的块的个数
用类似数位DP的方式，先去掉k的限制，求出总方案，显然是$m^n$，然后减去不符合的方案总数
这个时候就可以DP了
设$f_i$为第1~i位满足条件的方案数
当$i<k$时，$f_i=f_{i-1}\times m;$
当$k \leq i$时，$f_i=(f_{i-k+1}-f_{i-1})\times (m-1);$（第$i-k$位必须与第$i-k+1$到第i位不同，所以因此乘$(m-1)$）
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
inline ll read() {
ll res=0,fh=1;
char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
if(ch=='-')fh=-1,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
return fh*res;
}
const int maxn=1000010;
const ll mod=1e9+7;
ll f[maxn];
int n,m,k;
ll tot,ans;
ll poww(ll n,ll m){
ll res=1;
while(m){
if(m&1) res*=n;
res%=mod;
n*=n;n%=mod;
m>>=1;
res%=mod;
}
return res;
}
int main(){
n=read(),m=read(),k=read();
tot=poww(m,n);
f[0]=1;
for(int i=1;i<k;i++){
f[i]=(f[i-1]*m)%mod;
ans+=f[i],ans%=mod;
}
for(int i=k;i<=n;i++){
f[i]=(ans*(m-1))%mod;
ans=(ans+f[i]-f[i-k+1]+mod)%mod;
}
return printf("%lld",(tot+mod-f[n])%mod),0;
}
```
[P3607 [USACO17JAN]Subsequence Reversal序列反转](https://www.luogu.org/problemnew/show/P3607)
序列反转？ splay！（大雾）
题意是求一个序列反转一次后的最长不降子序列
因为要求LIS，所以用DP（暴论）
对于一个区间$[l,r]$的答案，它的答案可以从哪些区间转移到呢？
一个经典的套路就是区间$[l+1,r],[l,r-1],[l+1,r-1]$转移出来，其中第三个较为少见
经过一些思考，我用$f_{l,r,maxx,minn}$来表示$maxx=max\{a_{1\rightsquigarrow l-1}\},minn=min\{a_{r+1\rightsquigarrow n}\}$，对区间$[l,r]$进行DP，每次把范围缩小一点
$f_{l,r,maxx,minn}$显然可以从区间$[l+1,r],[l,r-1],[l+1,r-1]$转移出来，详细转移见代码
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int INF=(1<<30);
inline int read() {
int res=0,fh=1;
char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
if(ch=='-')fh=-1,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
return fh*res;
}
inline int Max(int a,int b){
return a>b?a:b;
}
inline int Min(int a,int b){
return a<b?a:b;
}
const int maxn=60;
int n,a[maxn],f[maxn][maxn][maxn][maxn];
bool vis[maxn][maxn][maxn][maxn];
//f:max(1~l-1)=maxx min(r+1~n)=minn
inline int dfs(int l,int r,int maxx,int minn){
if(vis[l][r][maxx][minn]) return f[l][r][maxx][minn];
if(maxx>minn) return -INF;
if(l>r) return 0;
if(l==r){
return (a[l]>=maxx&&a[r]<=minn);
}
int ans=0;
ans=Max(ans,dfs(l+1,r,maxx,minn));
ans=Max(ans,dfs(l,r-1,maxx,minn));
if(a[l]>=maxx) ans=Max(ans,dfs(l+1,r,a[l],minn)+1);
if(a[r]<=minn) ans=Max(ans,dfs(l,r-1,maxx,a[r])+1);
//不交换
ans=Max(ans,dfs(l+1,r,maxx,minn));
if(a[r]>=maxx) ans=Max(ans,dfs(l+1,r-1,a[r],minn)+1);
if(a[l]<=minn) ans=Max(ans,dfs(l+1,r-1,maxx,a[l])+1);
if(a[r]>=maxx&&a[l]<=minn) ans=Max(ans,dfs(l+1,r-1,a[r],a[l])+2);
//交换
vis[l][r][maxx][minn]=1;
f[l][r][maxx][minn]=ans;
return ans;
}
int main(){
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
printf("%d\n",dfs(1,n,0,50));
return 0;
}
```
[P2501 \[HAOI2006\]数字序列](https://www.luogu.org/problemnew/solution/P2501)
好题哇，一二问都很有趣 窝想不出
题意是给一个序列，修改的数尽量少且使得修改后的序列满足单调上升 n3w5且数据纯随机
在此基础上，修改的幅度尽量小，输出最少修改的数和修改幅度之和
第一问，如果要保留$a_i$和$a_j(i<j)$，那么必须满足它们之间的数能够修改为合法
因为要求严格单调上升，那么$(a_j-a_i)$一定要大于$j-i$
移项得$a_j-j>a_i-i$，所以将每个$a_i$减去i，求新序列最长不下降子序列的长度，就是最多能保留的个数，与n的差即为答案
（这大概是个很常见的技巧了，在数位DP好像也很常见）
第二问，仍然将原序列按第一问的方法变换，那么我们要做的就是把b变得单调不降
因为我们求出来的新序列的最长不降子序列单调不降，于是对于不选入LIS的每个元素一定不在它左边最靠近它的被选入LIS的元素$b_l$，和右边最靠近它的被选入LIS的元素$b_r$ 形成的区间$[b_l,b_r]$ 中（如果在 那这个LIS就可以更长）
因为窝语文不好 又抄了一段题解里的话
>我们用f[i]表示前i个数要达到单调上升最少改动的幅度（最后答案为f[n]）.
>【中心思想】：若a[i],a[j] (i<j) 满足 a[j]-a[i]>=j-i , 那么[i,j]中一定存在一个k,使a[i ~ k]都变成a[i],a[k+1 ~ j]都变成a[j]时，a[i~j]单调上升且代价最小，这个其实可以想出个所以然，但严格的数学证明还是要参考楼下ydc神犇。至于这个k , 直接枚举即可 。 理论时间复杂度为O(n^3) ， 但实际远达不到 ， 加上数据随机 ， 是可以水过的。
[P3794 签到题IV](https://www.luogu.org/problem/P3794)
给定一个长度为n的序列$a$，让你数满足区间或和 异或上 区间gcd的值为k的区间个数
一看似乎毫无思路，但是发现随着元素数量的增加 gcd单调递减，或和 单调递增。于是我们可以利用这个性质，找出gcd值一定的情况（因为gcd递减），此时gcd xor k 为一定值，此后二分递增的or找出答案。主要的trick 是查询区间or 和区间 gcd 时可以采用st表
（这两个东西都属于重复区间答案不变的信息）
时间复杂度$O(nlog^2 n)$
[Atlantis HDU - 1542](http://acm.hdu.edu.cn/showproblem.php?pid=1542)
扫描线板子题，然而码了好久QAQ
虽然没有啥有趣的，但是是个非常可爱的科技
过程就不说了8
```cpp
/*
code by codesonic
time:2019/08/25 23:07:45
Title:HDU1542 - Atlantis
tag:Segment tree,Scanning line
*/
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int res=0,fh=1;
char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
if(ch=='-')fh=-1,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
return fh*res;
}
const int maxn=114514;
struct seg{
double l,r,h;int pos;
bool operator<(const seg &rhs)const {
return h<rhs.h;
}
}e[maxn<<1];//每一条线段 第h行，第l到r列，pos表示上下边界
struct segt{
int l,r;double sum;
int flag;
}t[maxn<<2];
int n,num,cnt;
double x[maxn<<1];
#define lson (rt<<1)
#define rson (rt<<1|1)
inline void pushup(int rt){
if(t[rt].flag) t[rt].sum=x[t[rt].r+1]-x[t[rt].l];
else if(t[rt].l==t[rt].r) t[rt].sum=0;
else t[rt].sum=t[lson].sum+t[rson].sum;
}
inline void build(int rt,int l,int r){
t[rt].l=l,t[rt].r=r;t[rt].sum=0,t[rt].flag=0;
if(l==r) return ;int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
}
inline void upd(int rt,int l,int r,int v){
if(l==t[rt].l&&r==t[rt].r){
t[rt].flag+=v;pushup(rt);
return ;
}
int mid=(t[rt].l+t[rt].r)>>1;
if(r<=mid) upd(lson,l,r,v);
else if(l>mid) upd(rson,l,r,v);
else upd(lson,l,mid,v),upd(rson,mid+1,r,v);
pushup(rt);
}
int main(){
int cas=0;
while(1){
num=cnt=n=0;
memset(e,0,sizeof e); memset(x,0,sizeof x); memset(t,0,sizeof t);
n=read();if(!n) return 0;
for(int i=1;i<=n;i++){
double x1,x2,y1,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
e[++num].l=x1,e[num].r=x2,e[num].h=y1,e[num].pos=-1;
e[++num].l=x1,e[num].r=x2,e[num].h=y2,e[num].pos=1;
x[++cnt]=x1,x[++cnt]=x2;
}
/***********/
sort(e+1,e+1+num);sort(x+1,x+1+cnt);
int tot=unique(x+1,x+1+cnt)-(x+1);
/***********///离散化
build(1,1,tot);double ans=0;
for(int i=1;i<=num;i++){
int l=lower_bound(x+1,x+1+tot,e[i].l)-x,
r=lower_bound(x+1,x+1+tot,e[i].r)-x-1;
upd(1,l,r,e[i].pos);
ans+=(e[i+1].h-e[i].h)*t[1].sum;
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",++cas,ans);
}
return 0;
}
/*
2
10 10 20 20
15 15 25 25.5
0
*/
```
[P2939 \[USACO09FEB\]改造路Revamping Trails()](https://www.luogu.org/problem/P2939)
一直很想巩固的图论拆点题，似乎是经典题。
把每个点拆成k个点，然后假设[u,v]之间有边，那第i层的u到第i+1层的v的边权为0
然后最多有k层...没了。
[P1810](https://www.luogu.org/problem/P1810)一道构造题，然而这道题还没加spj且数据问题比较大，但是std的构造方式非常巧妙。
相似的集合之和相差不会超过n，所以按照集合元素和模(n+1)相等的分一组就行了。
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int res=0,fh=1;
char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
if(ch=='-')fh=-1,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
return fh*res;
}
int n,m,k;
int main(){
scanf("%d%d%d",&n,&k,&m);
for(int i=1;i<=k;i++){
int sum=0;int x;
scanf("%d",&x);
for(int j=1;j<=x;++j) {
int a;
scanf("%d",&a);
sum+=a;
}
printf("%d\n",sum%(n+1)+1);
}
return 0;
}
```
[P3588 [POI2015]PUS](https://www.luogu.org/problem/P3588)
好题，对于这种限制某个元素比另一个元素大的题，我们通常都是在这个两个元素之间连一条边，判断有没有环。然后这题是在区间进行操作，对于这种题我们常常是通过建一个“超级节点”，然后让区间所有数都向他连边来解决。然而这样子每个区间需要最多建n条边，一共有m个区间，就产生了nm条边。
干脆换一种方式考虑，对于区间我们用线段树把他搞成log个节点（类似于线段树询问区间时遍历到的节点），然后用这log个节点相互连边就行了
一共log^2n条边，可以接受。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=7e6+10;
const int maxm=7e6+10;
const int INF=1000000000;
bool vis[maxn],ins[maxn];
int ls[maxn],rs[maxn],f[maxn],o[maxn];
int in[maxn],id[maxn],cnt=0;
struct node{int v,w,nxt;}G[maxm];int head[maxn],tot;
inline void addedge(int u,int v,int w){G[++tot]=(node){v,w,head[u]},head[u]=tot,in[v]++;}
queue<int> q;
inline void build(int rt,int l,int r){
if(l==r){id[l]=rt,cnt=max(cnt,rt);return;}
int mid=(l+r)>>1;ls[rt]=++cnt,rs[rt]=++cnt;
build(ls[rt],l,mid);build(rs[rt],mid+1,r);
addedge(rt,ls[rt],0);addedge(rt,rs[rt],0);
}
inline void que(int rt,int l,int r,int ql,int qr,int w){
if(ql<=l&&qr>=r){addedge(w,rt,1);return;}
int mid=(l+r)>>1;
if(ql<=mid)que(ls[rt],l,mid,ql,qr,w);
if(qr>mid) que(rs[rt],mid+1,r,ql,qr,w);
}
bool ok;
void dfs(int u){
vis[u]=ins[u]=1;
for(int i=head[u];i;i=G[i].nxt){
int to=G[i].v;
if(ins[to]) ok=0;if(!vis[to])dfs(to);
}
ins[u]=0;
}
int n,s,m,pr;
int main(){
scanf("%d%d%d",&n,&s,&m);
cnt=1;build(1,1,n);for(int i=1;i<=s;i++){int x;scanf("%d",&x);scanf("%d",&f[id[x]]);o[id[x]]=f[id[x]];}
for(int i=1;i<=m;i++){
int l,r,k;scanf("%d%d%d",&l,&r,&k);pr=l,++cnt;
for(int j=1;j<=k;j++){
int x;scanf("%d",&x);
addedge(id[x],cnt,0);
if(pr<=x-1) que(1,1,n,pr,x-1,cnt);pr=x+1;
}
if(pr<=r) que(1,1,n,pr,r,cnt);
}
for(int i=1;i<=cnt;i++) if(!f[i]) f[i]=INF;
for(int i=1;i<=cnt;i++) if(!vis[i]){
ok=1;dfs(i);
if(!ok)return puts("NIE"),0;
}
for(int i=1;i<=cnt;i++) if(!in[i]) q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=G[i].nxt){
int to=G[i].v,w=G[i].w;
in[to]--;
if(o[to]>f[u]-w)return puts("NIE"),0;
f[to]=min(f[to],f[u]-w);
if(!in[to]) q.push(to);
if(f[to]<1) return puts("NIE"),0;
}
}
puts("TAK");
for(int i=1;i<=n;i++) printf("%d ",f[id[i]]);
return puts(""),0;
}
```
[P1429 平面最近点对（加强版）](https://www.luogu.org/problem/P1429)
人类智慧题，贪心地想，两个点的x坐标尽量接近，那么距离也会变小（不考虑y坐标
于是随便将整个图旋转各种度数，然后按x坐标排序，然后每个点只考虑x坐标与它最接近的几个点计算答案
发现能过。而且也没想到什么卡法
（因为旋转度数未知）...
要学的还有将一个点（x,y）绕中心(a,b)旋转$\theta$度的方法
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
const double pi=acos(-1.0);
const int maxn=2e5+10;
double ans=1e15;
struct node{
double x,y;
}a[maxn];
inline bool cmp(node a,node b){
return a.x<b.x;
}
inline double dis(node a,node b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline void calc(){
for(int i=1;i<=n;i++)
for(int j=i+1;j<=i+6&&j<=n;j++)
ans=min(ans,dis(a[i],a[j]));
}
inline void maintain(double dg){
dg=dg/180.0*pi;
for(int i=1;i<=n;i++){
double x=a[i].x,y=a[i].y;
double xn,yn;
xn=x*cos(dg)-y*sin(dg);
yn=x*sin(dg)+y*cos(dg);
a[i].x=xn,a[i].y=yn;
}
sort(a+1,a+1+n,cmp);
calc();
}
int main(){
srand(114514);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
maintain(0);
maintain(114);
maintain(19);
maintain(19);
maintain(81);
return printf("%.4lf\n",ans),0;
}
```
[P5589 小猪佩奇玩游戏](https://www.luogu.org/problem/P5589)
不错的期望中档题
与之前做过的一堆题类似
假设一个点有$d_i$个点删掉，就能删掉它
那答案就是$\sum_{i=1}^n \frac{1}{d_i} $
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e9+1;
vector<int> v,p[200];
int T,n;
signed main(){
for(int i=2;i<=40000;i++){
for(int j=i*i;j<=maxn;j*=i)
v.push_back(j);
}
sort(v.begin(),v.end());
int lst=-1,cnt=0;
for(int i=0;i<v.size();i++){
if(v[i]!=lst&&lst!=-1){
p[cnt].push_back(lst);
cnt=0;
}
cnt++;
lst=v[i];
}
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
int tot=0;double ans=0;
for(int i=1;i<=10;i++){
int tmp=lower_bound(p[i].begin(),p[i].end(),n+1)-p[i].begin();
ans+=tmp*1.0/(i+1);
tot+=tmp;
}
ans+=1.0*(n-tot);
printf("%.8lf\n",ans);
}
}
```
[P3719 [AHOI2017初中组]rexp](https://www.luogu.org/problem/P3719)
虽然不算有趣的题，但是代码写起来看起来非常难
然而比较舒服的写法就非常有趣值得一学
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=114514;
inline int work(int now){
char c;
while(scanf("%c",&c)!=EOF){
if(c=='a') now++;
else if(c=='(') now+=work(0);
else if(c=='|') return max(now,work(0));
else if(c==')') return now;
}
return now;
}
int main(){
return printf("%d\n",work(0)),0;
}
```