A. Petya and Origami
Water.
#include <bits/stdc++.h>
using namespace std; #define ll long long
ll n, k; ll Get(ll x)
{
return (x * n) % k == ? (x * n) / k : (x * n) / k + ;
} int main()
{
while (scanf("%lld%lld", &n, &k) != EOF)
{
ll res = Get() + Get() + Get();
printf("%lld\n", res);
}
return ;
}
B. Margarite and the best present
Water.
#include <bits/stdc++.h>
using namespace std; #define ll long long
int q, l, r;
ll get(ll x)
{
return x * ((x & ) ? - : );
} int main()
{
while (scanf("%d", &q) != EOF)
{
for (int qq = ; qq <= q; ++qq)
{
scanf("%d%d", &l, &r);
if (l == r) printf("%lld\n", get(l));
else
{
ll res = ;
if ((l & ) == ) res = get(l++);
if (r & ) res += get(r--);
res += ((r - l + ) >> );
printf("%lld\n", res);
}
}
}
return ;
}
C. Masha and two friends
Upsolved.
题意：
有一个黑白相间的棋盘，第一次选择一个矩形区域将区域内所有格子染白
第二次选择一个矩形区域将所有格子染黑，求最后白方块个数和黑方块个数
思路：
考虑先求整个棋盘的黑白方块个数，再删除两块矩形的黑白方块个数，矩形交部分要加一次
再求染色后，增加的黑块和白块个数
考虑怎么求黑白相间的黑白方块个数，发现如果矩形有一边长为偶数，那么两种颜色数量相同
否则，左下角是什么颜色，这个颜色的方块就多一个
其实，只求一种颜色就好了，因为总数是不变的
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define pll pair <ll, ll>
int t; ll x[], y[], X[], Y[], n, m, white, black;
pll tmp; pll get(ll n, ll m, int vis)
{
++n, ++m;
pll res = pll(, );
if ((n & ) && (m & ))
{
res.first = res.second = ((n - ) * m) >> ;
res.first += (m >> ) + 1ll * (vis ^ );
res.second += (m >> ) + 1ll * vis;
}
else
res.first = res.second = (n * m) >> ;
return res;
} ll get2(ll n, ll m) { ++n, ++m; return n * m; } int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%lld%lld", &n, &m);
for (int i = ; i < ; ++i) scanf("%lld%lld", x + i, y + i);
tmp = get(n - , m - , );
white = tmp.first, black = tmp.second;
tmp = get(y[] - y[], x[] - x[], (x[] & ) ^ (y[] & ));
white -= tmp.first; black -= tmp.second;
tmp = get(y[] - y[], x[] - x[], (x[] & )^ (y[] & ));
white -= tmp.first, black -= tmp.second;
X[] = max(x[], x[]); X[] = min(x[], x[]);
Y[] = max(y[], y[]); Y[] = min(y[], y[]);
if (X[] > X[] || Y[] > Y[])
{
white += get2(x[] - x[], y[] - y[]);
black += get2(x[] - x[], y[] - y[]);
}
else
{
tmp = get(Y[] - Y[], X[] - X[], (X[] & ) ^ (Y[] & ));
white += tmp.first;
black += tmp.second;
white += get2(x[] - x[], y[] - y[]) - get2(X[] - X[], Y[] - Y[]);
black += get2(x[] - x[], y[] - y[]);
}
printf("%lld %lld\n", white, black);
}
return ;
}
D. Olya and magical square
Upsolved.
题意：
给出一个$2^n \cdot 2^n 的矩形，每次可以画一个十字，使得被划区域的矩形分成四部分，新矩形边长减半$
$求画了K刀之后，是否存在左下角矩形到右上角矩形的一条通路，使得经过的矩形边长都相等$
$如果有，输出log2(边长)$
思路：
先考虑最多能画多少刀
注意到第一次可以画一刀，第二次可以画四刀，一共可以画N次，是一个等比数列
$\frac {4^n - 1}{3}$
暴力去逼近使得 $\frac {4^n - 1}{3} <= k$
这个时候对存在的现有矩形都多画一刀就要超过k了
那么我们假设已经画了$tot刀，我们需要考虑怎么分配剩下的k - tot 刀$
我们可以保持一个长度为曼哈顿距离的通路，那么这个通路以外的矩形随便画
或者这条通路上的矩形都要画一次
分类讨论一下是否满足即可
#include <bits/stdc++.h>
using namespace std; #define ll long long
int t; ll n, k; bool ok(ll k, ll n, ll tmp)
{
ll tot = ;
if (k < ) return false;
for (int i = ; i <= n; ++i)
{
tot += tmp;
tmp *= ;
if (tot >= k) return true;
}
return false;
} int ok2(ll k, ll n, ll tmp)
{
ll tot = ;
for (int i = ; i <= n; ++i)
{
tot += tmp;
tmp *= ;
if (tot == k) return i;
if (tot > k) return -;
}
return -;
} int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%lld%lld", &n, &k);
ll tot = , tmp = ; int i;
for (i = ; i <= n; ++i)
{
tot += tmp * tmp;
tmp <<= ;
if (tot > k)
{
--i;
tmp >>= ;
tot -= tmp * tmp;
break;
}
else if (tot == k) break;
}
if (i > n) puts("NO");
else
{
if (i == n) printf("YES %d\n", );
else
{
//cerr << tot << " " << i << " " << tmp << endl;
int use;
if (ok(k - tot, n - i, tmp * tmp - tmp * + )) printf("YES %lld\n", n - i);
else if (ok(k - tot - (tmp * - ), n - i, tmp * tmp - tmp * + )) printf("YES %lld\n", n - i - );
else if ((use = ok2(k - tot, n - i, tmp * - )) != -) printf("YES %lld\n", n - i - use);
else puts("NO");
}
}
}
return ;
}
E. Sonya and Matrix Beauty
Upsolved.
题意：
有一个字符矩阵，对于一个子矩阵，对于每一行，可以任意改变字母顺序，使得每一行每一列都是回文串
那么这个子矩阵就是好矩阵，求有多少个子矩阵是好矩阵
思路：
先考虑一行，一行在改变顺序之后是回文串，那么其拥有奇数个字母的个数$<= 1$
再来考虑列，如果一个矩阵是好的矩阵
那么它的第一行中每种字母的个数和最后一行中要相同，第二行要和倒数第二行相同
注意到这和找回文串的思路很像
可以套用Manacher 算法的思路，$O(26n)处理$
再加上对于行的枚举
总的复杂度为$O(26n^3)$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 600
int n, m;
char s[N][N];
int cnt[N][];
int Mp[N]; bool okone(int x)
{
int res = ;
for (int i = ; i < ; ++i) res += cnt[x][i] & ;
return res <= ;
} bool ok(int x, int y)
{
for (int i = ; i < ; ++i) if (cnt[x][i] != cnt[y][i])
return false;
return true;
} int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
n <<= ;
for (int i = ; i <= n; i += ) scanf("%s", s[i] + );
ll res = ;
for (int l = ; l <= m; ++l)
{
memset(cnt, , sizeof cnt);
for (int r = l; r <= m; ++r)
{
memset(Mp, , sizeof Mp);
for (int i = ; i <= n; i += ) ++cnt[i][s[i][r] - 'a'];
int Max = , pos = -;
for (int i = ; i <= n; ++i)
{
if (!okone(i))
{
Mp[i] = ;
continue;
}
if (Max > i) Mp[i] = min(Mp[ * pos - i], Max - i);
else Mp[i] = ;
while (i >= Mp[i] && i + Mp[i] <= n && okone(i + Mp[i]) && okone(i - Mp[i]) && ok(i + Mp[i], i - Mp[i]))
{
++Mp[i];
}
if (i + Mp[i] > Max)
{
Max = i + Mp[i];
pos = i;
}
res += Mp[i] / ;
}
}
}
printf("%lld\n", res);
}
return ;
}
F. Katya and Segments Sets
Upsolved.
题意：
有n个集合，每个集合有若干个线段，每次询问一段连续的集合中，这些集合是否都有至少一条线段被$[l, r] 包含$
思路：
先考虑暴力，我们可以暴力枚举每个集合，所有$y <= r 中对应的x 的最大值是否 >= l$
然后考虑数据结构优化
先按r排序之后，再插入可持久化线段树之中。
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define M 300010
#define INF 0x3f3f3f3f
int n, q, m, k, brr[M << ];
struct qnode
{
int l, r, p;
void scan()
{
scanf("%d%d%d", &l, &r, &p);
brr[++m] = r;
}
bool operator < (const qnode &other) const
{
return r < other.r;
}
}qarr[M]; int GetHash(int x) { return lower_bound(brr + , brr + + m, x) - brr; }
void Hash()
{
sort(brr + , brr + + m);
m = unique(brr + , brr + + m) - brr - ;
for (int i = ; i <= k; ++i)
qarr[i].r = GetHash(qarr[i].r);
} namespace SEG
{
int T[M << ], cnt;
struct node
{
int ls, rs, Min;
}a[M * ];
void build(int &now, int l, int r)
{
now = ++cnt;
a[now].Min = ;
if (l == r) return;
int mid = (l + r) >> ;
build(a[now].ls, l, mid);
build(a[now].rs, mid + , r);
}
void update(int &now, int pre, int l, int r, int pos, int val)
{
now = ++cnt;
a[now] = a[pre];
if (l == r)
{
a[now].Min = max(a[now].Min, val);
return;
}
int mid = (l + r) >> ;
if (pos <= mid) update(a[now].ls, a[pre].ls, l, mid, pos, val);
else update(a[now].rs, a[pre].rs, mid + , r, pos, val);
a[now].Min = min(a[a[now].ls].Min, a[a[now].rs].Min);
}
int query(int now, int l, int r, int ql, int qr)
{
if (l >= ql && r <= qr) return a[now].Min;
int mid = (l + r) >> ;
int res = INF;
if (ql <= mid) res = min(res, query(a[now].ls, l, mid, ql, qr));
if (qr > mid) res = min(res, query(a[now].rs, mid + , r, ql, qr));
return res;
}
} int main()
{
while (scanf("%d%d%d", &n, &q, &k) != EOF)
{
for (int i = ; i <= k; ++i) qarr[i].scan(); Hash();
sort(qarr + , qarr + + k);
SEG::build(SEG::T[], , n);
for (int i = ; i <= k; ++i)
{
if (SEG::T[qarr[i].r] == ) SEG::T[qarr[i].r] = SEG::T[qarr[i].r - ];
SEG::update(SEG::T[qarr[i].r], SEG::T[qarr[i].r], , n, qarr[i].p, qarr[i].l);
}
for (int qq = , a, b, x, y; qq <= q; ++qq)
{
scanf("%d%d%d%d", &a, &b, &x, &y);
y = upper_bound(brr + , brr + + m, y) - brr - ;
int tmp = SEG::query(SEG::T[y], , n, a, b);
if (tmp >= x) puts("yes");
else puts("no");
if (qq == q) return ;
fflush(stdout);
}
}
return ;
}