• 欢迎光临~

# Content

## [CF912D]Fishes

(1le r le n,mle 10^5,1le k le min(ntimes m,10^5))

（也不知道为啥我会在 (texttt{graph}) 题单里看到这题 /yiw）

``````// Problem: CF912D Fishes
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF912D
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,m,r,k;
int a[maxn],b[maxn];
struct node {
int x,y;
node() {
x = y = 0;
}
node(int x,int y):x(x),y(y){}
bool operator < (const node& p)const {
return 1ll * a[x] * b[y] < 1ll * a[p.x] * b[p.y];
}
};
priority_queue<node> q;
unordered_map<int,bool> vis[maxn];
int main() {
scanf("%d %d %d %d",&n,&m,&r,&k);
for(int i = 1;i <= n - r + 1;++ i)++ a[i],-- a[i + r];
for(int i = 1;i <= m - r + 1;++ i)++ b[i],-- b[i + r];
for(int i = 1;i <= n;++ i)a[i] += a[i - 1];
for(int i = 1;i <= m;++ i)b[i] += b[i - 1];
sort(a + 1 , a + 1 + n , greater<int>());
sort(b + 1 , b + 1 + m , greater<int>());
q.emplace(1 , 1);
vis[1][1] = true;
long long ans = 0;
while(k --) {
auto [x , y] = q.top();
q.pop();
ans += 1ll * a[x] * b[y];
if(x < n&&vis[x + 1].find(y) == vis[x + 1].end()) {
vis[x + 1][y] = true;
q.emplace(x + 1 , y);
}
if(y < m&&vis[x].find(y + 1) == vis[x].end()) {
vis[x][y + 1] = true;
q.emplace(x , y + 1);
}
}
printf("%.10lfn",(double)(1.0 * (double)ans) / (double)(1.0 * (double)(n - r + 1) * (double)(m - r + 1)));
return 0;
}
``````

## [CF1056E]Check Transcription

(2le |t|le 10^5,1le |s|le 10^6)

`SA` 的解法，但我 `SA` 太渣想不到 QAQ。

（我并没有直接去枚举那个出现次数较多的，这样虽然时间复杂度不标准但也能过）

### Code

``````// Problem: CF1056E Check Transcription
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1056E
// Memory Limit: 250 MB
// Time Limit: 3000 ms
//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 5;
const int maxm = 1e5 + 5;
const ll p = 13331;
const ll mod = 1e9 + 7;
char t[maxn],s[maxn];
unsigned long long Hash[maxn],pw[maxn];
int n,m;
int main() {
scanf("%s %s",t + 1,s + 1);
m = strlen(t + 1);
n = strlen(s + 1);
pw[0] = 1;
Hash[0] = 0;
for(int i = 1;i <= n;++ i) {
pw[i] = pw[i - 1] * p % mod;
(Hash[i] = Hash[i - 1] * p % mod + s[i]) % mod;
}
int ans = 0;
int cnt1 = 0,cnt2 = 0;
for(int i = 1;i <= m;++ i)cnt1 += t[i] == '0',cnt2 += t[i] == '1';
for(int len1 = 1;len1 <= (n - cnt2) / cnt1;++ len1) {
int len2 = (n - cnt1 * len1) / cnt2;
if(len1 * cnt1 + len2 * cnt2 != n)continue ;
int cur = 0,st1 = 0,st2 = 0;
bool flag = true,flag1 = false,flag2 = false;
for(int i = 1;i <= m;++ i) {
if(!flag)break ;
if(t[i] == '0') {
if(flag1)flag &= ((Hash[cur + len1] - Hash[cur] * pw[len1] % mod + mod) % mod == (Hash[st1 + len1] - Hash[st1] * pw[len1] % mod + mod) % mod);
else st1 = cur,flag1 = true;
cur += len1;
}
else {
if(flag2)flag &= ((Hash[cur + len2] - Hash[cur] * pw[len2] % mod + mod) % mod == (Hash[st2 + len2] - Hash[st2] * pw[len2] % mod + mod) % mod);
else st2 = cur,flag2 = true;
cur += len2;
}
if(flag1&&flag2)flag &= ((Hash[st1 + len1] - Hash[st1] * pw[len1] % mod + mod) % mod != (Hash[st2 + len2] - Hash[st2] * pw[len2] % mod + mod) % mod);
}
ans += flag;
}
printf("%d",ans);
return 0;
}
``````

## [CF1093G]Multidimensional Queries

(n)(k) 维的点 (a_1ldots a_n)​，两点 ((x_1,x_2,ldots,x_k​),(y_1​,y_2​,ldots,y_k​))间的曼哈顿距离为 (sumlimits_{i=1}^k |x_i-y_i|)

(Q) 次操作，操作分两种：

• (1 i b_1 b_2,ldots,b_k)​，表示将 (a_i) 修改为 ((b_1,b_2,ldots,b_k))

• (2 l r)，表示询问 ([l,r]) 内最大的两点间曼哈顿距离。

(1 le n,Q le 2times 10^5,1le kle 5)

(2^k) 棵线段树，第 (x) 棵线段树中的叶子结点就表示 (x) 的二进制位对应的点的权值。

(ans = maxlimits_{iin [0,2^{k-1})} f(i)+f(2^{k}-1-i))

### Code

``````// Problem: CF1093G Multidimensional Queries
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1093G
// Memory Limit: 500 MB
// Time Limit: 6000 ms
//

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int maxk = 5;
int n,k,x;
int a[maxn][maxk];
int b[maxk];
struct Segment_Tree {
int ls[maxn << 2],rs[maxn << 2],sum[maxn << 2];
void pushup(int i) {
sum[i] = max(sum[i << 1] , sum[i << 1 | 1]);
return ;
}
void build(int i,int l,int r) {
ls[i] = l;
rs[i] = r;
sum[i] = -1e9;
if(l == r) {
sum[i] = 0;
for(int j = 0;j < k;++ j)sum[i] += (x >> j & 1) ? a[l][j] : -a[l][j];
return ;
}
int mid = l + r >> 1;
build(i << 1 , l , mid);
build(i << 1 | 1 , mid + 1 , r);
pushup(i);
return ;
}
void modify(int i,int pos) {
if(ls[i] == rs[i]) {
sum[i] = 0;
for(int j = 0;j < k;++ j)sum[i] += (x >> j & 1) ? b[j] : -b[j];
return ;
}
int mid = ls[i] + rs[i] >> 1;
if(pos <= mid)modify(i << 1 , pos);
else modify(i << 1 | 1 , pos);
pushup(i);
return ;
}
int query(int i,int l,int r) {
if(ls[i] >= l&&rs[i] <= r) {
return sum[i];
}
if(ls[i] > r||rs[i] < l)return -1e9;
int mid = ls[i] + rs[i] >> 1,s = -1e9;
if(l <= mid)s = max(s , query(i << 1 , l , r));
if(r > mid)s = max(s , query(i << 1 | 1 , l , r));
return s;
}
}tr[32];
int main() {
scanf("%d %d",&n,&k);
for(int i = 1;i <= n;++ i)
for(int j = 0;j < k;++ j)scanf("%d",&a[i][j]);
for(x = 0;x < (1 << k);++ x)tr[x].build(1 , 1 , n);
int Q;
scanf("%d",&Q);
int S = (1 << k) - 1;
while(Q --) {
int op,i,l,r;
scanf("%d",&op);
if(op & 1) {
scanf("%d",&i);
for(int j = 0;j < k;++ j)scanf("%d",&b[j]);
for(x = 0;x < (1 << k);++ x)tr[x].modify(1 , i);
}
else {
scanf("%d %d",&l,&r);
int ans = -1e9;
for(x = 0;x < (1 << (k - 1));++ x)ans = max(ans , tr[x].query(1 , l , r) + tr[S ^ x].query(1 , l , r));
printf("%dn",ans);
}
}
return 0;
}
``````

upd：晚上交互题居然做出来了，可惜一开始脑抽，复杂度实现错了，不然排名能高好多的 QAQ。

## [CF1713D]Tournament Countdown

（注：写题解时 system test 还未进行，如果 fst 了就看个乐吧 qwq）

(2^n) 个人打淘汰赛。(1) 号和 (2) 号打，(3) 号和 (4) 号打，依次类推。

• `? a b`，表示询问 (a) 号和 (b) 号胜利次数的关系。(1) 表示 (a) 赢的次数比 (b) 多，(2) 表示 (a) 赢的次数比 (b) 少，(0) 表示 (a,b) 胜利次数相同。

(1le nle 17)

• 结果为 (1)：也就是 (c_1gt c_3= 0)，说明 (c_1 = 1)，也就是说 (1)(2) 的比赛中 (1) 一定胜利了，否则 (c_1) 不可能为 (1)。那 (2) 就没有询问的必要了，直接询问下 (1 4) 即可。

• 结果为 (2)：和上面类似。

• 结果为 (0)：即 (c_1=c_3=0)，那就可以推出来 (c_2=c_4=1)，询问 (2 4) 即可。

1. 首先特判 (n=1) 的情况，直接用一次询问得出答案。

2. (n gt 1)，就把 (2^n) 拆成 (2^{n-2})(4) 人小组，用我们上面的算法判断，得出 (2^{n-2}) 个胜者，再递归到 (n-2) 的情况求解。

（老觉得这个东西很怪，可能有问题，请大佬们帮忙看看 QAQ）

# Code

``````// Problem: D. Tournament Countdown
// Contest: Codeforces - Codeforces Round #812 (Div. 2)
// URL: https://codeforces.com/contest/1713/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//

#include <bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define Chtholly set<node>::iterator
#define SET set<int>::iterator
#define VEC vector<int>::iterator
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 5e5 + 5;
const int maxm = 3e6 + 5;
const int maxk = 30;
const ll mod = 1e9 + 7;
const int INF = 1e9;
const ll INFll = 1e16;
int n;
std::vector<int> s;
int p;
printf("? %d %dn",a,b);
fflush(stdout);
scanf("%d",&p);
return p;
}
void solve(int n) {
if(n <= 1) {
printf("! %dn",ask(s[0] , s[1]) == 1 ? s[0] : s[1]);
fflush(stdout);
return ;
}
else if(n == 2) {
int p = ask(s[0] , s[3]);
if(p == 1) {
printf("! %dn",ask(s[0] , s[2]) == 1 ? s[0] : s[2]);
fflush(stdout);
}
else if(p == 2) {
printf("! %dn",ask(s[1] , s[3]) == 1 ? s[1] : s[3]);
fflush(stdout);
}
else {
printf("! %dn",ask(s[1] , s[2]) == 1 ? s[1] : s[2]);
fflush(stdout);
}
return ;
}
vector<int> G;
for(int i = 0;i < (1 << n);i += 4) {
int p = ask(s[i] , s[i + 2]);
if(p == 1) {
G.pb(ask(s[i] , s[i + 3]) == 1 ? s[i] : s[i + 3]);
}
else if(p == 2) {
G.pb(ask(s[i + 2] , s[i + 1]) == 1 ? s[i + 2] : s[i + 1]);
}
else {
G.pb(ask(s[i + 1] , s[i + 3]) == 1 ? s[i + 1] : s[i + 3]);
}
}
s = G;
solve(n - 2);
return ;
}
void work() {
scanf("%d",&n);
s.clear();
for(int i = 1;i <= (1 << n);++ i)s.pb(i);
solve(n);
return ;
}
int main() {
int T;
scanf("%d",&T);
while(T --)work();
return 0;
}
``````