4.10省选模拟
状态确实不是很好,希望最后几场考试能认真对待吧
\(T1\)一开始想了个\(n^2log,\)也想到了\(trie\)树合并,但是确实不会求贡献,一直觉得合并完之后还要\(dp\)一遍,下了场之后,听\(zwaire\)一说可以在合并时候求贡献取个最大就好了,顿悟,直接在合并时候在有一边\(siz=1\)是时候遍历一下就好了,确实没想到
\(T2\)提交答案,简单玩了几组,后面几个过于麻烦就弃了
\(T3\)神仙题.
\(T1\)
直接大力\(01trie\)合并统计贡献即可
#include
#define ls tr[x].son[0]
#define rs tr[x].son[1]
using namespace std;
struct node{
int siz,val,son[2];
}tr[2000010];
int n,tot,rts[100010],ans[100010];
vector road[100010];
int init(int v,int dep=17)
{
int x=++tot;
tr[x].siz=1;
if(dep) tr[x].son[v>>dep-1&1]=init(v,dep-1);
return x;
}
int find(int x,int y,int dep)
{
int res=0;
while(dep)
{
int ch=!ls;
x=tr[x].son[ch];
if(tr[y].son[ch]) y=tr[y].son[ch];
else res|=1< \(T2\)
\(1.in\):只有一个未知项,暴力枚举
\(2.in:\)同\(1\)(想桃子),模数互质,直接\(CRT\)合并
\(3.in:guass\)消元
\(4.in:2^n\)暴力枚举
\(5.in:\)发现模数不是质数了,那么考虑分别高斯消元+\(CRT\)合并或者高斯消元时候使用辗转相减法不必考虑逆元(我倾向于写辗转相减,好写)
\(6.in:\)同\(5\)
\(7.in:dp\)判断可行性即可
\(8.in:\)和\(6\)一样,但是有两个不能同时满足
\(9.in:\)我也是暴力枚举过的(貌似正解是求众数)
\(10,in:\)大力搜索....
\(T3\)
怎么也看不出来是个\(dp...\)
\(AGC022F\)原题的\(n<=40,\)模拟赛\(n<=500,O(n^4)\)过不了
题目大意\(:\)
给定坐标轴上一些点,每次任选两个点,删去一个,另一个点移动到关于被删点对称的位置,问最后所以的情况数
首先考虑对于每一种情况,输者向赢者连边,那么最后连出来是一棵树的样子
考虑即使最后一棵树确定了,但是他的方案数不一定唯一(类似于拓扑序不唯一,但并不一致),其实就可以看成是对于赢者位置取正负,这样方案能够一一对应,那么我们实际的方案数就是当前树每个点\(c_i\)的取值了
待补