如题，主要是总结给自己看的= =不算题解。
过题/补题数 6/9
（绝对不是摸鱼被push了所以赶在第二场之前补了题然后令人感慨想小小总结一下）
按照我的开题顺序和难度综合的顺序复盘了一下解法和思考过程。
A-World Final? World Cup! (I) https://ac.nowcoder.com/acm/contest/46800/A
水题，模拟，签到（昼伏夜出人士刚睡醒刨完饭赶来WA了三发是谁我不说）
设置了四个变量分别存储AB剩余球的数量和已经进了的球的数量，对输入逐位进行模拟。
WA就在WA在提前结束比赛的判断语句应该在每个循环末尾都进行一次，而不是哪个队得分之后才进行判断。（一定是没睡醒，嗯）
C-现在是，学术时间 (I) https://ac.nowcoder.com/acm/contest/46800/C
应该也是签到，主要考思维（与A题开出来的时间隔了20多分钟是因为盯着B题发了会儿呆最终遗憾离场）
鉴于其成立的条件很明显可以知道，获得的学术水平只会小于等于教授有的论文数量，所以直接每位教授一份论文就是最优解。
H-本题主要考察了DFS https://ac.nowcoder.com/acm/contest/46800/H
思维题签到，感觉比上一道还要简单一些
由于整块拼图的总面积已知，缺失和多余的面积也知道，直接用总面积减去已知面积就能得出所求的一块的面积。
L-本题主要考察了运气 https://ac.nowcoder.com/acm/contest/46800/L
数学的签到，虽然也可以超级罚时运气出来（）
向来比较怕求数学期望的问题（之前打比赛碰到就没写出来过几道），但是这道比较简单
本蒟蒻的方法就是把对于【这个角色的团队和第几个人】可能出现的情况都列举了一下，分别计算了每种情况的猜测次数
猜测的最优方法肯定是先猜团队再猜第几个人，就假设都从1开始往大了猜
只需要注意一下猜到第4队时，无论对错都能得到结果，猜到每队第3个人时也是。
K-本题主要考察了dp https://ac.nowcoder.com/acm/contest/46800/K
众所周知标题里有什么这道题就一定不会考什么（）
个人感觉是一道非常有codeforces风格的贪心
稍微画画就能知道，按照100100的方法先初始化整个数组，如果1的个数小于等于这样初始化需要的1的个数，则直接输出0（这样排列不会出现坏区间）
如果还有多的1就全部放在右边，即从最右边开始，见到0就改成1，这样形成的字符串再遍历求一下坏区间有多少个，输出就完了。
D-现在是，学术时间 (II) https://ac.nowcoder.com/acm/contest/46800/D
分类讨论的模拟，因为要分类讨论所以有点麻烦，花了一些时间，但读懂就能写
无论p在哪儿，都跟与它距离最远的【所给矩形的一个顶点】组成第二个矩形，这样能确保结果最大。
主要针对点的选择进行分类讨论，并且计算面积的时候细心一点就ok
以上就是本菜狗赛时做出来的所有题目orz别骂了别骂了
除了第一题脑子抽了WA了三发其他都是一发过，罚时很少还可以（）
接下来是，幻想补题时间！
M-本题主要考察了找规律 https://ac.nowcoder.com/acm/contest/46800/M
嘴上说着“众所周知标题里有什么这道题就一定不会考什么”然后信以为真以为它有规律的屑！！！
找到了一个很有道理的规律甚至用了点小学数学知识证明了一下，然后WA了5发
然后写了个dfs找出了很多不对的例子（）然后又给dfs疯狂剪枝然后T了3发
为什么就不能往dp想呢（可莉疑惑）完全看不出dp的屑（有被诈骗到）
赛后分析了一下恍然大悟发现如此简单= =写了下注释，非常板子
#include<bits/stdc++.h>
using namespace std;
const int N=600;
int n,m;
double f[N][N];//f[i][j]表示分到第i个朋友和分出去j个仙贝时获得的友情最大值
int main()
{
cin>>n>>m;//朋友数、仙贝数
for(int i=1;i<=n;i++)//分到第i个朋友
{
for(int j=0;j<=m;j++)//已经分出去了j个仙贝（包括第i个人在内）
{
for(int k=0;k<=j;k++)//枚举第i个朋友分到的仙贝数量
f[i][j]=max(f[i][j],f[i-1][j-k]+1.0*k/(m-(j-k)));
//【分到第i-1个朋友和分出去j-k时的友情最大值】加上【第i个朋友分k个仙贝的值】
//枚举取最大值
}
}
printf("%.9lf",f[n][m]);
return 0;
}
总之是dp还需要刷题了orz知道了知道了别骂了别骂了
G-鸡格线 https://ac.nowcoder.com/acm/contest/46800/G
一眼线段树，并且跟之前做过的一道题有异曲同工之妙 https://www.acwing.com/activity/content/problem/content/6664/
赛时改了下代码，T了2发，遗憾离场（）
线段树板子比较好写，主要是没有找到如何优化
这道题优化需要看出f(x)表达式具有收敛性，在x=0，99，100时运算之后值不会变
根据这一点判断当前区间上的值需不需要修改。
具体在结构体里添加flag变量标记该区间上已经不需要修改的数的数量，如果该数量等于区间长度，则不需要对该区间进行修改。
想出来之后就十分简单，感觉裸线段树就优化比较难，有的时候需要创造性思维一下（）
其实优化方法跟之前写过的题也是差不多的，但写之前那道题的时候并没有太注意收敛的问题，再加上年代久远已经快忘了当初的优化条件，所以gg
发现了数学的重要性（）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
ll n,m;
ll w[N];
struct Node{
ll l,r;
ll v;
ll flag;//添加变量flag用于记录该区间上有多少数已经不需要进行操作（已收敛）
}tr[N*4];
void pushup(ll u)
{
tr[u].v=tr[u<<1].v+tr[u<<1|1].v;
tr[u].flag=tr[u<<1].flag+tr[u<<1|1].flag;//pushup时需要更新flag的值
}
void build(ll u,ll l,ll r)
{
if(l==r) tr[u]={l,r,w[r]};
else
{
tr[u]={l,r};
ll mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(ll u,ll l,ll r,ll k)
{
if(tr[u].flag==tr[u].r-tr[u].l+1) return;//只要该区间上所有数都不需要修改，则直接return
if(tr[u].l==tr[u].r&&tr[u].l>=l&&tr[u].r<=r)
{
for(ll i=1;i<=k;i++)
{
tr[u].v=round(10*sqrt(tr[u].v));
if(tr[u].v==0||tr[u].v==99||tr[u].v==100) //对该数的收敛进行判断
{
tr[u].flag=1;//讲该数标记为不再需要修改
break;
}
}
}
else
{
ll mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,k);
if(r>mid) modify(u<<1|1,l,r,k);
pushup(u);
}
}
ll query(ll u,ll l,ll r)
{
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v;
else
{
ll mid=tr[u].l+tr[u].r>>1;
ll res=0;
if(l<=mid) res=query(u<<1,l,r);
if(r>mid) res+=query(u<<1|1,l,r);
return res;
}
}
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(ll i=1;i<=n;i++) cin>>w[i];
build(1,1,n);
while(m--)
{
int opt;
cin>>opt;
if(opt==1)
{
ll x,y,k;
cin>>x>>y>>k;
modify(1,x,y,k);
}
else cout<<query(1,1,n)<<"\n";
}
return 0;
}
F-鸡玩炸蛋人 https://ac.nowcoder.com/acm/contest/46800/F
并查集，加了些思维
并查集还是比较好看出来的，主要是被思维困住了
赛时看了一下，求个数不会，下一位orz
补题的时候一开始以为赛时读错了题，然后发现并没有读错，但是理解错了，理解得极其复杂所以不会写orz
比较显然的结论赛时还是看出来了的：如果炸弹都在同一个连通块中，那么有解，如果不是在同一个连通块中就无解。
但是对于求解的个数犯了难，没想清楚移动和放炸蛋本质上是两种操作：并不是移动到某一个地点就一定要放了炸蛋才走的。
又由于不能移动到放了炸蛋的地方，所以赛时以为这是个图论题（）想了一下不知道怎么求，于是去T线段树了。
实际上由于移动不一定需要放炸蛋，所以把每个点作为起点和终点都是可以的
只要想清楚了这个，整个题就变成了并查集近似板子题
先对所有边进行连通处理，同时用num函数记录每个连通块的点的数量
然后分三种情况处理：
1.全图都没有炸蛋，即输入的最后一行全都为0
-此时随便把炸蛋人放进哪个连通块让它随便跑都是可以的，输出结果即为所有连通块的结点数的平方相加
2.有炸蛋来自不同的连通块
-此时无论怎么移动，炸蛋人都不可能从一个连通块跑到另一个连通块去放炸蛋，所以一定无解，输出0
3.所有炸蛋都在同一个连通块中
-此时有解，输出这个连通块的结点数的平方
补题时因为把find(i)错写成f[i]，WA到怀疑人生的屑= =
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300010;
ll f[N];
ll num[N];
ll a[N];
ll find(ll x)
{
if(f[x]!=x) return f[x]=find(f[x]);
return x;
}
int main()
{
ll n,m;
cin>>n>>m;
for(ll i=1;i<=n;i++) {f[i]=i;num[i]=1;}
while(m--)
{
ll u,v;
cin>>u>>v;
if(u>v) swap(u,v);
ll x=find(u),y=find(v);
if(x!=y)
{
f[x]=y;
num[y]+=num[x];
}
}
ll res=0;
map<int,int> mp;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==0) continue;
if(mp[find(i)]==0) res++;//记录有炸蛋的连通块的数量
mp[find(i)]=1;
}
ll ans=0;
if(res==0)//对应情况1
{
for(ll i=1;i<=n;i++)
if(find(i)==i) ans+=num[i]*num[i];
}
else if(res==1)//对应情况3
{
for(ll i=1;i<=n;i++)
{
if(a[i]!=0) {ans+=num[find(i)]*num[find(i)];break;}
}
}
cout<<ans;//情况2则不修改ans值，直接输出初值0
return 0;
}
后面的题有缘再补吧= =要是能补出来后面再来接着写
小小总结一下：
1.鼠鼠还是写不来dp捏，感觉不是很把握得住这种比较玄幻的东西，总之多刷题吧
2.线段树裸题主要难点在优化和加一些其他小算法的组合（比如前缀和什么的），做的时候多观察条件，找到优化条件。目前暂时还没达到用线段树处理一些更高级的题的水平，所以多做几道这样的题多思考一下（）
3.这次比赛对于前面题的罚时比较满意，过题数不是很满意，说明需要学新的东西，练一下思维了。别原了多看看远处的abc和cf吧家人们= =
蒟蒻碎碎念完毕，开溜~（可能下一场打完再写一个碎碎念）
