22暑期多校补题
day1
G 字典序最大值
按照字典序定义，保证除最后一位都为9，即n为最大值；否则n.size-1位数的全是9的大数为更优最大值
for(int i=0;i<s.size()-1;i++){
if(s[i]!='9'){f=0;break;}
}
if(f)cout<<s;
else {
for(int i=0;i<s.size()-1;i++)cout<<9;
}A 区间合并
对原区间进行补充及合并使得原区间合并成一个连续区间，给出所补区间长度
sort(a.begin(),a.end());
ll res=0;
int r=a[0].second;
for(int i=1;i<n;i++){
if(a[i].first<=r)r=max(a[i].second,r);
else res+=a[i].first-r,r=a[i].second;
}D 几何最大值
对特殊情况进行观察，寻找弦最大值
double dis=sqrt(x*x+y*y);
double an=abs(acos((dis-d)/r)),bn=abs(acos((dis+d)/r));
printf("%.12lf\n",r*abs(an-bn));day2
G n的最小递增递减排列
令i * i为>=n的最小数，对排列进行观察发现，以i为划分数量的由连续的i个数递增或递减形成排列，其符合题目要求的最小，如n=7，i=3，3 2 1 6 5 4 7。在xoy坐标系中画出，这样的线会更加清晰。
void solve(){
int n;
cin>>n;
int l=1,r=1000;
while(l<r){
int mid=l+r>>1;
if(a[mid]>=n)r=mid;
else l=mid+1;
}
int k=0,t=l;
for(int i=1;i<=n;i++){
while(k+t>n)t--;
cout<<t+k<<' ';
if(t==1)t=l,k+=l;
else t--;
}
cout<<endl;
}其中a[i]等于i * i。
J线性回归
根据题目所求公式，自然联想到线性回归，根据线性回归方程的求法可以轻松得出本题结果。
注意需要将求和公式中得后半部分放在求和公式中写，防止值溢出
void solve()
{
int n;
n = gti();
double Vy = 0;
for (int i = 1; i <= n; i++)
a[i] = gti(),
Vy += a[i];
Vy /= n;
double Vx = ((double)n + 1.0) / 2.0, cnt = 0, res = 0, A = 0, B = 0;
for (int i = 1; i <= n; i++)
{
cnt += (i-Vx)*(a[i]-Vy);
res += (i - Vx) * (i - Vx);
}
A = cnt/ res;
B = Vy - A * Vx;
res = 0;
for (int i = 1; i <= n; i++)
{
res += (a[i] - A * i - B) * (a[i] - A * i - B);
}
printf("%.9lf\n", res);
}
K 三维DP
可以看成两个字符串的匹配，b字符串前i个字符和a字符串前j个字符完成匹配，再加入一维k表示当前匹配中剩余的未匹配的左括号数量，就可不重不漏的表示所有状态。当前状态向后传递，判断当加左括号时,当a[j+1]='(',则f[i+1][j+1][k+1]+=f[i][j][k],否则f[i+1][j][k+1]+=f[i][j][k]，同理判断右括号。
注意对三维数组f初始化时，只初始化所用部分即可，否则被卡
void solve()
{
int n, m;
string s;
cin >> n >> m >> s;
s = "!" + s;
vector< vector < vector<ll> > > f(m+5,vector< vector<ll> >(m+5,vector<ll>(m+5,0ll)));
f[0][0][0] = 1;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n + 1; j++)
{
for (int k = 0; k <= i; k++)
{
if (f[i][j][k])
{
int t = j + (s[j + 1] == '(');
(f[i + 1][t][k + 1] += f[i][j][k]) %= mod;
t = j + (s[j + 1] == ')');
if(k)(f[i + 1][t][k - 1] += f[i][j][k]) %= mod;
}
}
}
}
cout << f[m][n][0] << endl;
}D 二分找负环
可以将题目抽象为一个图，物品之间转换看成起点与终点，代价看为边权。二分找系数w，使得这个图上的环上权值积不大于1。又值太大，故可以对其取log使得取积可以变为求和，同时只要判断无负环即可。其中找负环可用bellman。
bool check(double x)
{
edge Edge[N];
for (int i = 0; i < m; i++)
{
Edge[i] = (edge){e[i].u, e[i].v, log(e[i].w * x)};
}
for(int i=1;i<=n;i++)dis[i]=-1e9;
dis[1] = 0;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < m; j++)
{
dis[Edge[j].v]=max(dis[Edge[j].u]+Edge[j].w,dis[Edge[j].v]);
}
}
for (int j = 0; j < m; j++)
{
if (dis[Edge[j].v] < dis[Edge[j].u] + Edge[j].w)
return 0;
}
return 1;
}
void solve()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
e[i] = (edge){b, d, (c * 1.0) / a};
}
double l = 0, r = 1;
while (l + 1e-7 < r)
{
double mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
printf("%.12lf\n", l);
}A
day3
C 字符串排序
通过观察可以发现正常情况下只要按字符串排序即可，但存在一种特殊情况就是，在两个字符串a，b的长度不同，且其中较短的字符串是另一个的前缀时，需要特殊判断。如果全部都是特殊判断会tle。
bool cmp(string a,string b){
if(a.size()!=b.size()&&a.substr(0,min(a.size(),b.size()))==b.substr(0,min(a.size(),b.size()))){
return a+b<b+a;
}
return a<b;
}
void solve()
{
int n;
cin>>n;
vector<string> s(n);
for(int i=0;i<n;i++)cin>>s[i];
sort(s.begin(),s.end(),cmp);
for(int i=0;i<n;i++)cout<<s[i];
}A LCA前后缀
倍增求LCA，可以发现在没有去除某一个点时，无法知道剩余关键点的LCA，故可以预处理前后缀LCA，然后依次枚举去除某个关键点的情况，为该关键点前后缀的LCA。
int cnt=0;
int cnt1=0;
int head[N],d[N],p[N][21];//head数组就是链接表标配了吧？d存的是深度（deep）,p[i][j]存的[i]向上走2的j次方那么长的路径
int head1[N],d1[N],p1[N][21];
struct node{
int v,next;
}e[N],e1[N];//存树
void add(int u,int v)
{
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt++;
} //加边函数
void add1(int u,int v)
{
e1[cnt1].v=v;
e1[cnt1].next=head1[u];
head1[u]=cnt1++;
}
void dfs(int u,int fa)
{
d[u]=d[fa]+1;
p[u][0]=fa;
for(int i=1;(1<<i)<=d[u];i++)
p[u][i]=p[p[u][i-1]][i-1];
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if(v!=fa)
dfs(v,u);
}
} //首先进行的预处理，将所有点的deep和p的初始值dfs出来
void dfs1(int u,int fa)
{
d1[u]=d1[fa]+1;
p1[u][0]=fa;
for(int i=1;(1<<i)<=d1[u];i++)
p1[u][i]=p1[p1[u][i-1]][i-1];
for(int i=head1[u];i!=-1;i=e1[i].next)
{
int v=e1[i].v;
if(v!=fa)
dfs1(v,u);
}
}
int lca(int a,int b) //非常标准的lca查找
{
if(d[a]>d[b])
swap(a,b); //保证a是在b结点上方，即a的深度小于b的深度
for(int i=20;i>=0;i--)
if(d[a]<=d[b]-(1<<i))
b=p[b][i]; //先把b移到和a同一个深度
if(a==b)
return a; //特判，如果b上来和就和a一样了，那就可以直接返回答案了
for(int i=20;i>=0;i--)
{
if(p[a][i]==p[b][i])
continue;
else
a=p[a][i],b=p[b][i]; //A和B一起上移
}
return p[a][0]; //找出最后a值的数字
}int lca1(int a,int b) //非常标准的lca查找
{
if(d1[a]>d1[b])
swap(a,b); //保证a是在b结点上方，即a的深度小于b的深度
for(int i=20;i>=0;i--)
if(d1[a]<=d1[b]-(1<<i))
b=p1[b][i]; //先把b移到和a同一个深度
if(a==b)
return a; //特判，如果b上来和就和a一样了，那就可以直接返回答案了
for(int i=20;i>=0;i--)
{
if(p1[a][i]==p1[b][i])
continue;
else
a=p1[a][i],b=p1[b][i]; //A和B一起上移
}
return p1[a][0]; //找出最后a值的数字
}
void solve()
{
memset(head,-1,sizeof(head));
memset(head1,-1,sizeof(head1));
int n,k;
cin>>n>>k;
vector<int> a(n+1),b(n+1),s(k+1);
for(int i=1;i<=k;i++)cin>>s[i];
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<=n;i++){
int v;
cin>>v;
add(v,i);
}
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=2;i<=n;i++){
int v;
cin>>v;
add1(v,i);
}
dfs(1,0);
dfs1(1,0);
vector<int> suA(k+1),suB(k+1),prA(k+1),prB(k+1);
suA[k]=s[k];
suB[k]=s[k];
prA[1]=s[1];
prB[1]=s[1];
for(int i=2;i<=k;i++)prA[i]=lca(s[i],prA[i-1]),prB[i]=lca1(s[i],prB[i-1]);
for(int i=k-1;i>=1;i--)suA[i]=lca(s[i],suA[i+1]),suB[i]=lca1(s[i],suB[i+1]);
int ct=0;
for(int i=1;i<=k;i++){
if(i==1){
ct+=a[suA[2]]>b[suB[2]];
}
else if(i==k){
ct+=a[prA[k-1]]>b[prB[k-1]];
}
else {
ct+=a[lca(suA[i+1],prA[i-1])]>b[lca1(suB[i+1],prB[i-1])];
}
}
cout<<ct<<endl;
}J 01dfs
对于此题可以将两相连十字路口的边看成点然后从一个点可以右转弯向令一个点的权重处理为0，其他的处理为1。从初始点开始dfs，将右转弯的点插入队列的前端，其余点插入队列后端，保存路径值，最终通过终点的路径值判断，是否到达终点，等的红绿灯又为多少。
typedef struct
{
int x, y, w;
} node;
int v[N][4], dis[N][4];
int sx, sy, ex, ey;
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < 4; j++)
{
cin >> v[i][j];
dis[i][j] = N;
}
}
cin >> sx >> sy >> ex >> ey;
deque<node> q;
q.push_back({sx, sy, 0});
while (q.size())
{
node t = q.front();
q.pop_front();
if (!sy)
continue;
int r;
for (int i = 0; i < 4; i++)
{
if (v[t.x][i] == t.y)
r = i;
}
if (dis[t.x][r] <= t.w)
continue;
dis[t.x][r] = t.w;
for (int i = 0; i < 4; i++)
{
if (v[t.y][i] == t.x)
r = (i + 1) % 4;
}
for (int i = 0; i < 4; i++)
{
if (i == r)
q.push_front({t.y, v[t.y][i], t.w});
else
q.push_back({t.y, v[t.y][i], t.w + 1});
}
}
int res;
for (int i = 0; i < 4; i++)
if (v[ex][i] == ey)
res = dis[ex][i];
if(res!=N)cout << res << endl;
else cout<<-1<<endl;
}day4
N 方差
通过对题目过程的几次模拟可以发现，进行题目给定的操作，不会使在二进制表示下的两数的每一位上1的总数减少，即虽然两值改变，但其和不变，同时可以发现，在许多次这样的操作后，所有位置上的1会向一些数富集，即使得一些数尽可能的大。
void solve()
{
ll n;
cin >> n;
vector<int> bit(20);
ll sum = 0;
for (int i = 0; i < n; i++)
{
ll x;
cin >> x;
sum += x;
for (int j = 0; j < 20; j++)
{
if (x & (1 << j))
bit[j]++;
}
}
ll A = sum * sum;
for (int i = 0; i < n; i++)
{
ll x = 0;
for (int j = 0; j < 20; j++)
{
if (bit[j])
bit[j]--, x += 1 << j;
}
A += (n * x - 2 * sum) * x;
}
if (A)
{
ll t = __gcd(A, n * n);
A /= t;
ll p = n * n / t;
cout << A << '/' << p << endl;
}
else
cout << "0/1" << endl;
}K 模运算
根据模运算性质若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)，故求i可以令A=i-1，同时前一步的结果对后一步的操作无影响。又在n个连续的数中必然有可以对n去摸得到i，题目中的操作可以保证，我们在进行第lg(n)次操作时，可以取到i，故我们只要枚举过程到lg(n)次即可，如果提前取到i便停止。很容易想到只要用满足想要取到的值，在目前最小的值和最大的值的取模区间内即可。
void solve()
{
int n;
cin >> n;
int size = ceil(log10(n));
ll cnt = 0;
if (n == 1)
cout << 0 << endl;
else
{
for (int i = 1; i <= n; i++)
{
ll t=10,s=i-1;
for(int j=1;j<=size;j++){
s*=10;
int r=((i-s)%n+n)%n;
if(r<t){cnt+=j;break;}
t*=10;
}
}
cout << cnt << endl;
}
}H 方块分配
将所有矩形的面积之和求出，然后又越接近正方形，其周长越短，故可以找出结果矩形的长宽。然后就是贪心的放进矩形，先放长的，长的放完或放不下了再放短的，直到填满，可以一行一行放入，一行填满再填下一行。
void solve()
{
int n;
cin >> n;
int area = n * (n + 1) * (n + 2) / 6;
multiset<int> a;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n + 1 - i; j++)
a.insert(i);
int w = area;
for (int i = 1; i * i <= area; i++)
if (area % i == 0)
w = area / i;
cout << 2 * (w + area / w) << endl;
for (int i = 0; i < area / w; i++)
{
int cur = 0;
while (cur < w)
{
auto it = a.upper_bound(w - cur);
--it;
cout << cur << ' ' << i << ' ' << cur + (*it) << ' ' << i + 1 << endl;
cur += (*it);
a.erase(it);
}
}
}D 三维dp
可以定义一个状态表示函数为f[i][j][k]，表示，第i家公司的IQ小于等于j，EQ小于等于k的最低的AQ的大小。在读入时，将f[i][j][k]=min(f[i][j][k],AQ)防止出现已经读入，并且较大的值覆盖小的值*。状态转移方程为，f[i][j][k]=min(f[i][j][k],f[i][j-1][k],f[i][j][k-1]) 。这样便可以O(1)的找到某人是否能在该公司找到工作。
*注意题目给的代码放在seed读入后
ll work(int a, int b, int c)
{
ll cnt=0;
for(int i=0;i<n;i++){
if(f[i][a][b]<=c)cnt++;
}
return cnt;
}
void solve()
{
ll seed;
cin >> n >> q;
memset(f, 0x3f, sizeof(f));
for (int i = 0; i < n; i++)
{
int m;
cin >> m;
while (m--)
{
ll a, b, c;
cin >> a >> b >> c;
f[i][a][b] = min(c,f[i][a][b]);
}
}
for (int i = 0; i < n; i++)
{
for (int j = 1; j <= 400; j++)
{
for (int k = 1; k <= 400; k++)
{
f[i][j][k] = min(f[i][j][k], min(f[i][j - 1][k], f[i][j][k - 1]));
}
}
}
cin >> seed;
mt19937 rng(seed);
uniform_int_distribution<> u(1, 400);
ll lastans = 0, res = 0;
for (int i = 1; i <= q; i++)
{
ll IQ = (u(rng) ^ lastans) % 400 + 1; // The IQ of the i-th friend
ll EQ = (u(rng) ^ lastans) % 400 + 1; // The EQ of the i-th friend
ll AQ = (u(rng) ^ lastans) % 400 + 1; // The AQ of the i-th friend
lastans = work(IQ, EQ, AQ); // The answer to the i-th friend
(res += lastans * qpow(seed, q - i, mod) % mod) %= mod;
}
cout << res << endl;
}day6
G 模拟画图
可以先处理背景，再处理字母。将字母分为横线，竖线和斜线处理。将每条线的起始坐标找出，再按照其对应长度填入即可。
可以找到部分规律减少代码量，同时所有的长度及坐标应该用包含n的表达式
void solve(){
int n;
cin>>n;
int len=13*n+19,wid=4*n+5;
for(int i=1;i<=len;i++){
for(int j=1;j<=wid;j++){
if(i==1||i==len||j==1||j==wid)a[j][i]='*';
else a[j][i]='.';
}
}
int c[10]={n+3,3*n+5,4*n+7,7*n+11,10*n+15,12*n+17},co=6;
pair<int,int> r[10]={{n+2,4*n+7},{2*n+3,4*n+7},{3*n+4,7*n+11},{n+2,10*n+15},{2*n+3,10*n+15},{3*n+4,10*n+15}};
int ro=6;
for(int i=0;i<co;i++){
for(int j=n+2;j<=3*n+4;j++){
a[j][c[i]]='@';
if(i==4&&j==2*n+3)i++;
}
}
int t=2*n+3;
for(int i=0;i<ro;i++){
int p=t,x=r[i].first,y=r[i].second;
while(p--)a[x][y++]='@';
}
for(int i=n+2,j=n+3;i<=3*n+4;i++,j++)a[i][j]='@';
for(int i=1;i<=wid;i++){
for(int j=1;j<=len;j++)cout<<a[i][j];
cout<<endl;
}
}J 改变数字
B可以变成A-B（令D=A-B），则可以由B，D交替做B-C使的C的值保持一直变化(当B！=D)，并且可由其过程推出以下公式：
C=k * (D-B)+C
C=k * (B-D)+B-C
C=k * (B-D)+D-C
其中k为任意整数
只要保证x满足以上任一一式即可
void solve() {
int a,b,c,x;
cin>>a>>b>>c>>x;
int d=a-b;
if(d==b){
if(x!=c&&x!=b-c)cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
else {
if(abs(x-c)%abs(b-d)&&abs(x-b+c)%abs(b-d)&&abs(x-d+c)%abs(b-d))cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
}B 树上差分
从根结点开始dfs，用栈记录下遍历路径，以当前结点位置为i，当第i-d[stk[i]]-1位置存在时，差分中该位置的值--。最后i结点的值加上子节点的值即为结果值。
题目应用双向线段
int dfs(int n){
st[n]=1;
stk[tt++]=n;
if(tt-d[n]-2>=0)cnt[stk[tt-d[n]-2]]--;
int res=0;
for(auto c:node[n])if(!st[c])res+=dfs(c);
tt--;
cnt[n]+=res;
return cnt[n];
}M DP
题目给出对于每一步只能向左或者向下走，即状态dp[i][j]只受dp[i+1][j]和dp[i][j+1]影响，故用dp可写。对于保证赢和保证输两种情况，只要保证在先手的时候可以赢（输），在后手的时候必须赢（输），即(i+j)%2==1,dp[i][j]=dp[i+1][j]||dp[i][j+1];(i+j)%2==0,dp[i][j]=dp[i][j+1]&&dp[i+1][j];
保证平局则需要先手平局和后手必须平局，表达式与上式相反。
注意：需要特判i==n和j==m
void solve() {
int n, m;
cin >> n >> m;
memset(dp, false, sizeof dp);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char c;
cin >> c;
if (c == 'A')
dp[0][i][j] = true, dp[2][i][j] = true;
if (c == 'B')
dp[1][i][j] = true, dp[2][i][j] = true;
}
}
for (int k = 0; k < 2; k++)
for (int i = n; i > 0; i--) {
for (int j = m; j > 0; j--) {
if (!dp[2][i][j]) {
if ((i + j) % 2) {
if ((dp[k][i + 1][j] && dp[k][i][j + 1]) ||
(j == m && dp[k][i + 1][j]) || (i == n && dp[k][i][j + 1]))
dp[k][i][j] = true;
} else if (dp[k][i + 1][j] || dp[k][i][j + 1])
dp[k][i][j] = true;
}
}
}
for (int i = n; i > 0; i--) {
for (int j = m; j > 0; j--) {
if (!dp[2][i][j]) {
if ((i + j) % 2 == 0) {
if ((dp[2][i + 1][j] && dp[2][i][j + 1]) ||
(j == m && dp[2][i + 1][j]) || (i == n && dp[2][i][j + 1]))
dp[2][i][j] = true;
} else if (dp[2][i + 1][j] || dp[2][i][j + 1])
dp[2][i][j] = true;
}
}
}
if (dp[0][1][1])
cout << "yes" << ' ';
else
cout << "no" << ' ';
if (!dp[2][1][1])
cout << "yes" << ' ';
else
cout << "no" << ' ';
if (dp[1][1][1])
cout << "yes" << ' ';
else
cout << "no" << ' ';
cout << endl;
}A 排数
将题目中的公式等价变形为 ,又
,其中log2 ai向下取整。
则可以将每个ai处理成2的幂的形式，排序找到最大的幂，就是m，然后再数组中插入i即可。
void solve() {
int n;
cin>>n;
vector<pair<int,int>> a(n);
for(int i=0;i<n;i++){
int k;
cin>>k;
k=two[int(log(k)/log(2))];
a[i]={k,i+1};
}
sort(a.begin(),a.end());
int m=a.back().first;
vector<int> res(m);
int blank=0;
for(auto c:a){
while(blank<m&&res[blank])blank++;
for(int i=blank;i<m;i+=c.first)res[i]=c.second;
}
for(int i=0;i<m;i++)if(!res[i])res[i]=1;
cout<<m<<endl;
for(int i=0;i<m;i++)cout<<res[i]<<' ';
cout<<endl;
}其中two数组为2的幂
I 多维处理
观察可以看出只要在当前维度（向量）处理时，在当前的d-1个点上都创建一遍迁移维度的所有点即可。同时，为了保证不重不漏，需要将原向量代表的角度进行去重处理，且在每加入一个维度时，使得该维度的区间长度比上一维度多31倍。而使用set就可以轻松完成去重和排序。
void solve() {
int n, d;
cin >> n >> d;
set<pair<ll, ll>> a;
for (int i = 0; i < n; i++) {
ll x, y;
cin >> x >> y;
a.insert({x/__gcd(x,y), y/__gcd(x,y)});
}
set<pair<ll, ll>> res;
res.insert({0, 0});
ll t = 1;
for (auto b:a) {
auto c=res;
ll x = t * b.first, y = t * b.second;
for (int j = 1; j < d; j++) {
ll x1 = x * j, y1 = y * j;
for (auto q:c)
res.insert({q.first + x1, q.second + y1});
}
t *= 31;
}
cout << res.size() << endl;
for (auto c : res)
cout << c.first << ' ' << c.second << endl;
}day7
C 创造排列
观察可知，只要a数组中数字不是全部相同即可创建如题排列，可以先创造一个bi=i的排列，然后对此排列进行调整，即双指针l=1,r=n遍历，当a[l]=b[l]，a[r]=b[r],r!=l时交换b[l]和b[r],最后当l==r,b[l]=a[l],再次遍历一遍a数组，找到a[i]!=b[l],交换b[i]和b[l]。
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
bool f = true;
for (int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = i;
if (a[i] != a[i - 1] && i != 1)
f = false;
}
if (f)
cout << "NO" << endl;
else {
cout << "YES" << endl;
int l = 1, r = n;
while (l < r) {
while (l < r && b[l] != a[l])
l++;
while (l < r && b[r] != a[r])
r--;
if (l < r)
swap(b[l++], b[r--]);
}
if (a[l] == b[l]) {
for (int i = 1; i <= n; i++)
if (a[i] != b[l]) {
swap(b[i], b[l]);
break;
}
}
for (int i = 1; i <= n; i++)
cout << b[i] << ' ';
cout << endl;
}
}F 祖玛游戏
根据题意我们可以在输入的时候就对数组进行处理，保证数组中间不会出现可以消除的值，之后就可以只对头尾消除即可。使用双端队列，否则会超时。
void solve() {
int n, x,cnt=0;
cin >> n >> x;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
if(tt-hh>=0&&(stk[tt]==t||stk[tt]+t==x)){
tt--,cnt++;
}
else stk[++tt] = t;
}
while(tt-hh>0&&(stk[hh]==stk[tt]||stk[hh]+stk[tt]==x)){
cnt++;
hh++,tt--;
}G 正则表达式
可以发现.*和.+可以表示所有的长度大于1的字符串，则可以发现令字符串长度为n，种类数为num，n==1时，num=2；n==2，当字符串中字母相同时，num==8反之num==6；n>2,当字符串中字母相同时，num==4反之num==2。
void solve() {
string s;
cin>>s;
bool f=true;
for(int i=1;i<s.size();i++)if(s[i]!=s[i-1]){f=false;break;}
int n=s.size();
if(n==1)cout<<"1 2"<<endl;
else if(n==2){
if(f)cout<<"2 8"<<endl;
else cout<<"2 6"<<endl;
}
else {
if(f)cout<<"2 4"<<endl;
else cout<<"2 2"<<endl;
}
}day8
F 数字LCS
题目要求按公式自己创造数组a和数组b，又公式对p取余，故当a数组和b数组中出现相同数字时，该数字后的所有数字相同，故只要找到a和b数组中最早出现的相同数字即可。
void solve()
{
int n,m;
ll p,x,a,b,c;
cin>>n>>m>>p>>x>>a>>b>>c;
map<int,int> f;
for(int i=0;i<n;i++){
x=(a*(x*x%p)%p+b*x%p+c)%p;
int t=(int)x;
if(f.find(t)==f.end())f[t]=i;
}
int res=0;
for(int i=0;i<m;i++){
x=(a*(x*x%p)%p+b*x%p+c)%p;
int t=(int)x;
if(f.find(t)!=f.end())res=max(res,min(m-i,n-f[t]));
}
cout<<res<<endl;
}day9
A 双指针保持区间内有m个不同的数
先找到一个满足题意的区间，移动其左指针，同时在仍然合法的情况下，不需要移动右指针，同时加上区间右边的所剩值的个数为该左指针的贡献；当区间不合法时就需要移动右指针以保证区间合法。
void solve()
{
int n,m;
cin>>n>>m;
vector<int> a(n);
map<int,int> b;
for(int i=0;i<n;i++)cin>>a[i];
ll cnt=0,p=0;
for(int i=0,j=0;i<n;i++){
while(j<n&&p!=m){
if(!b[a[j]])p++;
b[a[j]]++;
j++;
}
if(p==m){
cnt+=n-j+1;
b[a[i]]--;
if(!b[a[i]])p--;
}
else break;
}
cout<<cnt<<endl;
}B 概率dp+差分
我们可以知道在第i步第j个荷叶上，可以在第i+1步等概率向[j+1,j+aj]区间上任意荷叶跳去。即区间[i+1][j+1,j+aj]上概率全部加f[i][j]/ai，即可以用差分表示，再做一下前缀和，就可求出每一步概率，最后把所有能到第n个荷叶的概率求平方和即可。
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i < n; i++)
cin >> a[i];
inv[1] = 1;
for (int i = 2; i <= n; i++)
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
f[0][1] = 1;
for (int i = 0; i <= n; i++)
{
if (i)
for (int j = 2; j <= n; j++)
(f[i][j] += f[i][j - 1]) %= mod;
if (i != n)
for (int j = 1; j < n; j++)
{
(f[i + 1][j + 1] += inv[a[j]] * f[i][j]) %= mod;
f[i + 1][j + a[j] + 1] += mod - inv[a[j]] * f[i][j] % mod;
}
}
ll res = 0;
for (int i = 1; i <= n; i++)
(res += f[i][n] * f[i][n] % mod) %= mod;
cout << res << endl;
}G 双哈希和马拉车（烂了）（好像是双哈希要预处理？）
马拉车找到字符串中所有的回文串，并将这些回文串双哈希存一下，同时判断是否是公共回文串。
pair<ull, ull> make_hash(string s)
{
ull hsh1 = 0, hsh2 = 0;
for (int i = 0; i < s.size(); i++)
{
hsh1 = hsh1 * md1 + s[i] + 1;
hsh2 = hsh2 * md2 + s[i] + 1;
}
return {hsh1, hsh2};
}
void solve()
{
int k;
string s[6];
cin >> k;
for (int i = 1; i <= k; i++)
cin >> s[i];
set<pair<ull, ull>> a, b[6];
vector<int> q = manacher(s[1]);
for (int i = 2; i < q.size() - 1; i++)
{
int l = i - q[i] + 1, r = i + q[i] - 1;
while (l < r)
{
auto c = make_hash(s[1].substr(l, r - l + 1));
if (a.find(c) != a.end())
break;
a.insert(c);
r -= 2, l += 2;
}
}
if (k == 1)
{
cout << a.size() << endl;
return;
}
for (int i = 2; i <= k; i++)
{
q = manacher(s[i]);
for (int j = 2; j < q.size() - 1; j++)
{
int l = j - q[j] + 1, r = j + q[j] - 1;
while (l < r)
{
auto c = make_hash(s[i].substr(l, r - l + 1));
if (b[i].find(c) != b[i].end())
break;
if (a.find(c) != a.end())
b[i].insert(c);
r -= 2, l += 2;
}
}
}
int res = 0;
for (auto t : a)
{
for (int i = 2; i <= k; i++)
{
if (b[i].find(t) == b[i].end())
break;
if (i == k)
res++;
}
}
cout << res << endl;
}E 创造排列找到m个最长上升子序列
发现2 1 4 3 6 5这样构造排列可以构造出2的x次方，又发现在在i 2 1 i 4 3 i 6 5在i的位置插入适当的值可以使得原式加上相应的2的y次方，如二进制表示的10101，可以表示为9 10 2 1 4 3 11 12 6 5 8 7。
void solve()
{
int n;
cin >> n;
if (n == 1)
cout << 1 << endl
<< 1 << endl;
else
{
vector<int> a;
int mn;
while (n)
{
a.push_back(n % 2);
n /= 2;
}
for (int i = 0; i < a.size(); i++)
if (a[i])
{
mn = i;
break;
}
vector<int> b(2 * (a.size() - 1) + 1);
int t = 1;
for (int i = 1; i < a.size(); i++)
b[2 * i - 1] = t + 1, b[2 * i] = t, t += 2;
vector<int> res(101);
int cnt = 1, mx = b[b.size() - 2] + b[b.size() - 2] / 2 - mn, j = b.size() - 1;
t = a.size() - 2;
cout << mx << endl;
int i;
for (i = 100; i > 0 && j > 0;)
{
res[i--] = b[j--], res[i--] = b[j--];
if (a[t--])
{
while (cnt--)
res[i--] = mx--;
cnt = 0;
}
cnt++;
}
for (int i = 1; i <= 100; i++)
if (res[i])
cout << res[i] << ' ';
cout << endl;
}
}day5.5
M 模拟音游
按照相应系数模拟即可，注意是百分制
void solve()
{
double a[5][6], cnt[5] = {0};
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 5; j++)
{
cin >> a[i][j];
cnt[i] += a[i][j];
}
double xi[6][6] = {
0, 0, 0, 0, 0, 0,
0, 1, 1, 0.8, 0.5, 0,
0, 2, 2, 1.6, 1.0, 0,
0, 3, 3, 2.4, 1.5, 0,
0, 5, 5, 2.5, 2, 0,
0, 1, 0.5, 0.4, 0.3, 0};
double A = 0, B = cnt[4], A0 = 0, B0 = 0;
for (int i = 1; i <= 4; i++)
A += cnt[i] * xi[i][1];
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 5; j++)
A0 += a[i][j] * xi[i][j];
for (int j = 1; j <= 5; j++)
B0 += a[4][j] * xi[5][j];
printf("%.9lf\n", A0 / A * 100 + B0 / B);
}H 树上dp
通过观察可以发现，对于结点x，其子树上的结点的所有lca都是其本身，而非其子树上的结点的lca都是在其与根结点的一条不分支的通路上的某个祖先结点，故可以dp状态表示为第i结点的权值乘积约数中2的个数或5的个数，状态转移方程为dp[x]=dp[fa]+cnt[x]*(cnt2|5[x]-cnt2|5[fa])。最终结果为min(dp2[x],dp5[x])。
int dfs(int n)
{
if (st[n])
return 0;
st[n] = 1;
ccnt[n] = h[n].size();
if (n != 1)
ccnt[n]--;
for (auto c : h[n])
{
ccnt[n] += dfs(c);
}
return ccnt[n];
}
void dfs2(int n, int fa)
{
if (st[n])
return;
st[n] = 1;
int cnt = 0, fcnt = 0, t = n;
while (t % 2 == 0 && t)
{
cnt++, t /= 2;
}
t = fa;
while (t % 2 == 0 && t)
{
fcnt++, t /= 2;
}
dp2[n] = dp2[fa] + (ccnt[n] + 1) * (cnt - fcnt);
for (auto c : h[n])
if (!st[c])
dfs2(c, n);
}
void dfs5(int n, int fa)
{
if (st[n])
return;
st[n] = 1;
int cnt = 0, fcnt = 0, t = n;
while (t % 5 == 0 && t)
{
cnt++, t /= 5;
}
t = fa;
while (t % 5 == 0 && t)
{
fcnt++, t /= 5;
}
dp5[n] = dp5[fa] + (ccnt[n] + 1) * (cnt - fcnt);
for (auto c : h[n])
if (!st[c])
dfs5(c, n);
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
h[u].push_back(v);
h[v].push_back(u);
}
dfs(1);
memset(st, 0, sizeof(st));
dfs2(1, 0);
memset(st, 0, sizeof(st));
dfs5(1, 0);
while (m--)
{
int x;
cin >> x;
cout << min(dp2[x], dp5[x]) << endl;
}
}E 倒数第p个人
当一个人成为倒数第p个人时，他必然是亏的，故没有人会成为倒数第p个人，即剩下的人数为p的任意正整数次方时，没人会fudu，因为当他fudu就必然有人跟着fudu，就导致他可能会亏，所以这些人就不会fudu。同时位于n%p的人必然fudu，因为其不需要承担风险。
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
vector<int> b(n + 1);
int j = 1;
for (int i = 1; i <= n % m; i++)
b[i] = a[i][j++];
for (int i = 1; i <= n; i++)
cout << b[i] << ' ';
}
J 规律差分
将原数组进行差分（第一个元素减最后一个元素环状差分，同时保证数组中不出现负数），再观察有(1,1)->(2,0),(0,1)->(1,0),(2,1)->(0,0)，同时由(0,1)->(1,0)可以发现0并没什么实际用处，我们的目标就是通过(2,1)->(0,0)将数组整齐化，故1的数量要等于2的数量。那当1的数量大于2的数量呢，我们可以发现(1,1)->(2,0)，故大于2时同样可以。
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
int t = a[n], c;
for (int i = 1; i <= n; i++)
c = a[i], a[i] = (a[i] + 3 - t) % 3, t = c;
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; i++)
if (a[i] == 1)
cnt1++;
else if (a[i] == 2)
cnt2++;
if (cnt1 >= cnt2)
cout << "YES" << endl;
else
cout << "NO" << endl;
}day10
H 组合概率
本题求A赢得概率，其中随从可以忽略，只需要用A获胜的次数比上总场数即可，可以枚举所有A可以获胜的场次数，然后使用组合数去求出A获胜的次数，而此时总场数为2的场次数次幂。
void solve()
{
int a,b;
ll inv2=inv(2,mod);
cin>>a;
vector<int> t(7);
for(int i=0;i<7;i++)cin>>t[i];
cin>>b;
for(int i=0;i<7;i++)cin>>t[i];
(a+=9)/=10;
(b+=9)/=10;
ll res=0;
for(int i=0;i<a;i++){
(res+=(C(b+i-1,i)*qpow(inv2,b+i,mod))%mod)%=mod;
}
cout<<res<<endl;
}F bfs
cut先动手，故定义一个点集D为可以到达终点的点的集合，初始化t点在其中，故除了t点外只有满足有两条路可以到达集合D中的点可以加入点集D。
void solve()
{
memset(st, 0, sizeof(st));
memset(num, 0, sizeof(num));
for(int i=0;i<110;i++)a[i].clear();
cin >> n >> m >> s >> t;
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
queue<int> que;
que.push(t);
st[t]=1;
while (que.size())
{
int x = que.front();
que.pop();
for (auto c : a[x])
{
num[c]++;
if (num[c] >= 2 && !st[c])
st[c]=1,que.push(c);
}
}
if (num[s] >= 2)
cout << "Join Player" << endl;
else
cout << "Cut Player" << endl;
}I 数据范围
很容易发现在a数组中有两个一样的值和b数组中有两个一样的值时，只要输出这四个坐标即可，而当不存在这种情况时，我们可以将原式化简为求ai+bj=aj+bi，看上去感觉求出所有相加可能是一种T的做法，但是可以由数据范围保证我们进行操作最多不超过2e7，故可以暴力找出满足要求的结果。
void solve()
{
int n, m;
cin >> n >> m;
vector<pair<int, int>> a, b;
set<int> s;
bool f[2] = {false};
int ai, aj, bi, bj;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
if (s.find(x) != s.end())
{
f[0] = true, ai = i, aj = x;
continue;
}
s.insert(x);
a.push_back({x, i});
}
s.clear();
for (int i = 1; i <= m; i++)
{
int x;
cin >> x;
if (s.find(x) != s.end())
{
f[1] = true, bi = i, bj = x;
continue;
}
s.insert(x);
b.push_back({x, i});
}
if (f[1] && f[0])
{
for (int i = 0; i < a.size(); i++)
if (a[i].first == aj)
{
aj = a[i].se;
break;
}
for (int i = 0; i < b.size(); i++)
if (b[i].first == bj)
{
bj = b[i].se;
break;
}
cout << aj << ' ' << ai << ' ' << bj << ' ' << bi << endl;
}
else
{
bool f = false;
for (int i = 0; i < a.size(); i++)
{
for (int j = 0; j < b.size(); j++)
{
int sum = a[i].first + b[j].first;
if (t[sum].fi)
{
ai = min(a[i].se, t[sum].fi), aj = max(a[i].se, t[sum].fi);
bi = min(b[j].se, t[sum].se), bj = max(b[j].se, t[sum].se);
f = true;
break;
}
else
t[sum] = {a[i].se, b[j].se};
}
if (f)
break;
}
if (f)
cout << ai << ' ' << aj << ' ' << bi << ' ' << bj << endl;
else
cout << -1 << endl;
}
}E 匈牙利算法
本题为二分图最大匹配问题，只要将本题进行多次二分图最大匹配即可得出答案，对此我采用了匈牙利算法去做二分图最大匹配（随便搜个板子改改），只要保证不存在有人什么文件都不批阅即可。
bool search(int now) // 寻找增广路
{
for (int i = 1; i <= m; ++i)
{
if (eg[now][i] && !vis[i]) // 如果有边且这个边没有被走过
{
vis[i] = 1;
if (!use[i] || search(use[i]))
// 如果这个点没有被用过或者这个点可以给他提供位置（即有增广路）
{
use[i] = now;
return 1;
}
}
}
return 0;
}
int get()
{
fin >> m >> n;
bool t = 0;
for (int i = 1; i <= m; ++i)
{
string s;
cin >> s;
s = "." + s;
bool f = 0;
for (int j = 1; j <= n; j++)
{
if (s[j] == '1')
eg[j][i] = 1, f = 1; // 建边
}
if (!f)
t = 1;
}
if (t)
{
cout << -1 << endl;
return 0;
}
int cnt=m;
while(cnt){
for (int i = 1; i <= n; ++i)
{
memset(vis, 0, sizeof(vis));
cnt-=search(i); // 如果有增广路就将最大匹配+1（因为找到增广路匹配的边就会多1）
}
}
for(int i=1;i<=m;i++)cout<<use[i]<<' ';
return 0;
}
海康威视公司福利 1137人发布
投递钉钉信息等公司10个岗位