Educational CodeForces Round 1 (A~F) Solution
SlyCharlotte
·
·
个人记录
更好的阅读体验？
A. Tricky Sum
题意描述
给出一个 n，让你求出从 1 到 n 的和，但是其中每当遇到一个数是 2 的整数次幂时，就要变加为减。
简要分析
我们可以先计算 1\sim n 的和使用等差数列求和公式 \frac{n\times(n+1)} 2，随后再减去两倍的 1 \sim 2^x的和，使用等比数列求和公式 \frac{k^{x + 1} - 1}{(k-1)}。
时间复杂度 $O(T \log^2 n)$。
### 代码实现
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 7;
const ll INF = 1e9 + 7, MOD = 998244353;
inline ll read() {
char cCc;
ll xXx = 0, wWw = 1;
while (cCc < '0' || cCc > '9')
(cCc == '-') && (wWw = -wWw), cCc = getchar();
while (cCc >= '0' && cCc <= '9')
xXx = (xXx << 1) + (xXx << 3) + (cCc ^ '0'), cCc = getchar();
xXx *= wWw;
return xXx;
}
inline void write(ll xXx) {
if (xXx < 0)
putchar('-'), xXx = -xXx;
if (xXx > 9)
write(xXx / 10);
putchar(xXx % 10 + '0');
}
namespace FastIO {
class FastIOBase {
protected:
#ifdef OPENIOBUF
static const ll BUFSIZE=1<<22;
char buf[BUFSIZE+1];
ll buf_p=0;
#endif
FILE *target;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
FastIOBase(FILE *f) : target(f) {}
~FastIOBase() = default;
};
class FastOutput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
protected:
inline void __putc(char x) {
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
putc(x, target);
#endif
}
template<typename T>
inline void __write(T x) {
static char stk[64], *top;
top = stk;
if (x < 0) return __putc('-'), __write(-x);
do *(top++) = x % 10, x /= 10; while (x);
for (; top != stk; __putc(*(--top) + '0'));
}
public:
FastOutput(FILE *f = stdout) : FastIOBase(f) {}
#ifdef OPENIOBUF
inline void setTarget(FILE *f) { this->flush(),target=f; }
~FastOutput(){ flush(); }
#else
inline void setTarget(FILE *f) { target = f; }
#endif
template<typename ...T>
inline void writesp(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc(' '), 0)...}; }
template<typename ...T>
inline void writeln(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc('\n'), 0)...}; }
inline FastOutput &operator<<(char x) { return __putc(x), *this; }
inline FastOutput &operator<<(const char *s) {
for (; *s; __putc(*(s++)));
return *this;
}
inline FastOutput &operator<<(const string &s) { return (*this) << s.c_str(); }
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastOutput &operator<<(const T &x) { return __write(x), *this; }
} cout;
class FastInput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
protected:
inline char __getc() {
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
return buf[buf_p++];
#else
return getc(target);
#endif
}
public:
#ifdef OPENIOBUF
FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
FastInput(FILE *f = stdin) : FastIOBase(f) {}
inline void setTarget(FILE *f) { target = f; }
#endif
inline char getchar() { return __getc(); }
template<typename ...T>
inline void read(T &...x) { initializer_list<ll>{(this->operator>>(x), 0)...}; }
inline FastInput &operator>>(char &x) {
while (isspace(x = __getc()));
return *this;
}
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastInput &operator>>(T &x) {
static char ch, sym;
x = sym = 0;
while (isspace(ch = __getc()));
if (ch == '-') sym = 1, ch = __getc();
for (; isdigit(ch); x = (x << 1) + (x << 3) + (ch ^ 48), ch = __getc());
return sym ? x = -x : x, *this;
}
inline FastInput &operator>>(char *s) {
while (isspace(*s = __getc()));
for (; !isspace(*s) && *s && ~*s; *(++s) = __getc());
return *s = '\0', *this;
}
inline FastInput &operator>>(string &s) {
char str_buf[(1 << 8) + 1], *p = str_buf;
char *const buf_end = str_buf + (1 << 8);
while (isspace(*p = __getc()));
for (s.clear(), p++;; p = str_buf) {
for (; p != buf_end && !isspace(*p = __getc()) && *p && ~*p; p++);
*p = '\0', s.append(str_buf);
if (p != buf_end) break;
}
return *this;
}
} cin;
}
ll kissme(ll di, ll zhi) {
if (!zhi)return 1ll;
ll x = kissme(di, zhi >> 1);
if (zhi & 1)return x * x * di;
else return x * x;
}
void solve() {
ll n;
FastIO::cin >> n;
ll sum = n * (n + 1) / 2;
ll l = 0, r = 32;
while (l <= r) {
ll mid = (l + r) >> 1;
ll x = kissme(2, mid);
if (x <= n && x * 2 > n) {
l = mid;
break;
} else if (x > n)r = mid - 1;
else l = mid + 1;
}
sum -= 2 * (kissme(2, l + 1) - 1);
FastIO::cout << sum << '\n';
}
signed main() {
ll T;
FastIO::cin >> T;
while (T--)solve();
return 0;
}
```
## B. Queries on a String
### 题意描述
给你一个字符串 $s$，有 $m$ 次操作。
每次操作给定三个数 $l_i,r_i,k_i$ 表示在 $[l_i,r_i]$ 区间内循环右移 $k_i$ 次。
输出 $m$ 次操作后的子串。
### 简要分析
在区间 $[l_i,r_i]$ 内，若循环右移了 $r_i - l_i + 1$ 发现回到了原点。
于是循环右移 $k_i$ 次等价于循环右移 $k_i\mod {r_i - l_i + 1}$ 次。
模拟即可。
时间复杂度 $O(nm)$。
### 代码实现
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 7;
const ll INF = 1e9 + 7, MOD = 998244353;
inline ll read() {
char cCc;
ll xXx = 0, wWw = 1;
while (cCc < '0' || cCc > '9')
(cCc == '-') && (wWw = -wWw), cCc = getchar();
while (cCc >= '0' && cCc <= '9')
xXx = (xXx << 1) + (xXx << 3) + (cCc ^ '0'), cCc = getchar();
xXx *= wWw;
return xXx;
}
inline void write(ll xXx) {
if (xXx < 0)
putchar('-'), xXx = -xXx;
if (xXx > 9)
write(xXx / 10);
putchar(xXx % 10 + '0');
}
namespace FastIO {
class FastIOBase {
protected:
#ifdef OPENIOBUF
static const ll BUFSIZE=1<<22;
char buf[BUFSIZE+1];
ll buf_p=0;
#endif
FILE *target;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
FastIOBase(FILE *f) : target(f) {}
~FastIOBase() = default;
};
class FastOutput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
protected:
inline void __putc(char x) {
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
putc(x, target);
#endif
}
template<typename T>
inline void __write(T x) {
static char stk[64], *top;
top = stk;
if (x < 0) return __putc('-'), __write(-x);
do *(top++) = x % 10, x /= 10; while (x);
for (; top != stk; __putc(*(--top) + '0'));
}
public:
FastOutput(FILE *f = stdout) : FastIOBase(f) {}
#ifdef OPENIOBUF
inline void setTarget(FILE *f) { this->flush(),target=f; }
~FastOutput(){ flush(); }
#else
inline void setTarget(FILE *f) { target = f; }
#endif
template<typename ...T>
inline void writesp(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc(' '), 0)...}; }
template<typename ...T>
inline void writeln(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc('\n'), 0)...}; }
inline FastOutput &operator<<(char x) { return __putc(x), *this; }
inline FastOutput &operator<<(const char *s) {
for (; *s; __putc(*(s++)));
return *this;
}
inline FastOutput &operator<<(const string &s) { return (*this) << s.c_str(); }
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastOutput &operator<<(const T &x) { return __write(x), *this; }
} cout;
class FastInput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
protected:
inline char __getc() {
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
return buf[buf_p++];
#else
return getc(target);
#endif
}
public:
#ifdef OPENIOBUF
FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
FastInput(FILE *f = stdin) : FastIOBase(f) {}
inline void setTarget(FILE *f) { target = f; }
#endif
inline char getchar() { return __getc(); }
template<typename ...T>
inline void read(T &...x) { initializer_list<ll>{(this->operator>>(x), 0)...}; }
inline FastInput &operator>>(char &x) {
while (isspace(x = __getc()));
return *this;
}
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastInput &operator>>(T &x) {
static char ch, sym;
x = sym = 0;
while (isspace(ch = __getc()));
if (ch == '-') sym = 1, ch = __getc();
for (; isdigit(ch); x = (x << 1) + (x << 3) + (ch ^ 48), ch = __getc());
return sym ? x = -x : x, *this;
}
inline FastInput &operator>>(char *s) {
while (isspace(*s = __getc()));
for (; !isspace(*s) && *s && ~*s; *(++s) = __getc());
return *s = '\0', *this;
}
inline FastInput &operator>>(string &s) {
char str_buf[(1 << 8) + 1], *p = str_buf;
char *const buf_end = str_buf + (1 << 8);
while (isspace(*p = __getc()));
for (s.clear(), p++;; p = str_buf) {
for (; p != buf_end && !isspace(*p = __getc()) && *p && ~*p; p++);
*p = '\0', s.append(str_buf);
if (p != buf_end) break;
}
return *this;
}
} cin;
}
string s;
ll m;
signed main() {
FastIO::cin >> s;
FastIO::cin >> m;
while (m--) {
ll l, r, k;
FastIO::cin >> l >> r >> k;
ll len = r - l + 1;
k %= len;
string cur;
for (ll i = r - k; i <= r - 1; i++) {
cur += s[i];
}
for (ll i = l - 1; i < r - k; i++)cur += s[i];
for (ll i = l - 1, k = 0; i <= r - 1; i++)
s[i] = cur[k++];
}
FastIO::cout << s << '\n';
return 0;
}
```
## C. Nearest vectors
### 题意描述
有 $n$ 个点，每个点表示原点到该点的向量，让你求出两个向量最小的夹角，仅输出向量的序号。
### 简要分析
计算每个向量与 x 轴的夹角，使用 C++ 自带库函数 $atan(x,y)$ 计算，这里要处理负数角度的情况加上 $2\times \pi$ 即可。
结果保留并排序，枚举向量 $\mathbf{v_i},\mathbf{v_{i+1}}$ 取角度差的最小值即可。
注意到向量 $\mathbf{v_1}$ 与向量 $\mathbf{v_n}$ 也是相邻的不要忘记统计。
### 代码实现
```cpp
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 7;
const ll INF = 1e9 + 7, MOD = 998244353;
inline ll read() {
char cCc;
ll xXx = 0, wWw = 1;
while (cCc < '0' || cCc > '9')
(cCc == '-') && (wWw = -wWw), cCc = getchar();
while (cCc >= '0' && cCc <= '9')
xXx = (xXx << 1) + (xXx << 3) + (cCc ^ '0'), cCc = getchar();
xXx *= wWw;
return xXx;
}
inline void write(ll xXx) {
if (xXx < 0)
putchar('-'), xXx = -xXx;
if (xXx > 9)
write(xXx / 10);
putchar(xXx % 10 + '0');
}
namespace FastIO {
class FastIOBase {
protected:
#ifdef OPENIOBUF
static const ll BUFSIZE=1<<22;
char buf[BUFSIZE+1];
ll buf_p=0;
#endif
FILE *target;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
FastIOBase(FILE *f) : target(f) {}
~FastIOBase() = default;
};
class FastOutput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
protected:
inline void __putc(char x) {
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
putc(x, target);
#endif
}
template<typename T>
inline void __write(T x) {
static char stk[64], *top;
top = stk;
if (x < 0) return __putc('-'), __write(-x);
do *(top++) = x % 10, x /= 10; while (x);
for (; top != stk; __putc(*(--top) + '0'));
}
public:
FastOutput(FILE *f = stdout) : FastIOBase(f) {}
#ifdef OPENIOBUF
inline void setTarget(FILE *f) { this->flush(),target=f; }
~FastOutput(){ flush(); }
#else
inline void setTarget(FILE *f) { target = f; }
#endif
template<typename ...T>
inline void writesp(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc(' '), 0)...}; }
template<typename ...T>
inline void writeln(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc('\n'), 0)...}; }
inline FastOutput &operator<<(char x) { return __putc(x), *this; }
inline FastOutput &operator<<(const char *s) {
for (; *s; __putc(*(s++)));
return *this;
}
inline FastOutput &operator<<(const string &s) { return (*this) << s.c_str(); }
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastOutput &operator<<(const T &x) { return __write(x), *this; }
} cout;
class FastInput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
protected:
inline char __getc() {
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
return buf[buf_p++];
#else
return getc(target);
#endif
}
public:
#ifdef OPENIOBUF
FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
FastInput(FILE *f = stdin) : FastIOBase(f) {}
inline void setTarget(FILE *f) { target = f; }
#endif
inline char getchar() { return __getc(); }
template<typename ...T>
inline void read(T &...x) { initializer_list<ll>{(this->operator>>(x), 0)...}; }
inline FastInput &operator>>(char &x) {
while (isspace(x = __getc()));
return *this;
}
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastInput &operator>>(T &x) {
static char ch, sym;
x = sym = 0;
while (isspace(ch = __getc()));
if (ch == '-') sym = 1, ch = __getc();
for (; isdigit(ch); x = (x << 1) + (x << 3) + (ch ^ 48), ch = __getc());
return sym ? x = -x : x, *this;
}
inline FastInput &operator>>(char *s) {
while (isspace(*s = __getc()));
for (; !isspace(*s) && *s && ~*s; *(++s) = __getc());
return *s = '\0', *this;
}
inline FastInput &operator>>(string &s) {
char str_buf[(1 << 8) + 1], *p = str_buf;
char *const buf_end = str_buf + (1 << 8);
while (isspace(*p = __getc()));
for (s.clear(), p++;; p = str_buf) {
for (; p != buf_end && !isspace(*p = __getc()) && *p && ~*p; p++);
*p = '\0', s.append(str_buf);
if (p != buf_end) break;
}
return *this;
}
} cin;
}
template<typename T>
inline T Min(T x, T y) { return x < y ? x : y; }
template<typename T>
inline T Max(T x, T y) { return x > y ? x : y; }
template<typename T>
inline void Swap(T &x, T &y) {
T t = x;
x = y, y = t;
}
template<typename T>
inline T Abs(T x) { return x < 0 ? -x : x; }
inline ll gcd(ll a, ll b) {
return !b ? a : gcd(b, a % b);
}
inline ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
inline ll Pow(ll n, ll k) {
if (k < 0)return 0;
ll ret = 1, now = n;
while (k > 0) {
if (k & 1)ret *= now;
now *= now;
k /= 2;
}
return ret;
}
inline ll popcount(ll n) {
ll ret = 0, u = n;
while (u) {
ret += u % 2;
u /= 2;
}
return ret;
}
struct node {
ll x, y, id;
long double w;
} p[maxn];
bool cmp(node a, node b) {
return a.w < b.w;
}
const long double pi = acos(-1);
signed main() {
// freopen("code.in","r",stdin);
// freopen("code.out","w",stdout);
ll n;
FastIO::cin >> n;
for (ll i = 1; i <= n; i++) {
FastIO::cin >> p[i].x >> p[i].y;
p[i].w = atan2(p[i].x, p[i].y), p[i].id = i;
if (p[i].w < 0)p[i].w += 2 * pi;
}
sort(p + 1, p + 1 + n, cmp);
long double ans = p[1].w - p[n].w + 2 * pi;
ll x = p[1].id, y = p[n].id;
for (ll i = 1; i < n; i++)
if (p[i + 1].w - p[i].w < ans)
ans = p[i + 1].w - p[i].w, x = p[i].id, y = p[i + 1].id;
FastIO::cout << x << ' ' << y << '\n';
return 0;
}
```
## D. Igor In the Museum
### 题意描述
给你一个 $n \times m$ 的矩形，$k$ 次询问。
每次询问给定 $x,y$，求出点 $(x,y)$ 所在的联通块内相邻 # 的个数。
（这里注意，# 的个数可以重复计算！）
### 简要分析
搜索即可，但注意没搜索过一个联通块就要记下来该联通块的答案，避免重复搜索。
时间复杂度 $O(nm)$。
### 代码实现
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
const ll maxn = 1e3 + 7;
const ll INF = 1e9 + 7, MOD = 998244353;
const ll dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
inline ll read() {
char cCc;
ll xXx = 0, wWw = 1;
while (cCc < '0' || cCc > '9')
(cCc == '-') && (wWw = -wWw), cCc = getchar();
while (cCc >= '0' && cCc <= '9')
xXx = (xXx << 1) + (xXx << 3) + (cCc ^ '0'), cCc = getchar();
xXx *= wWw;
return xXx;
}
inline void write(ll xXx) {
if (xXx < 0)
putchar('-'), xXx = -xXx;
if (xXx > 9)
write(xXx / 10);
putchar(xXx % 10 + '0');
}
namespace FastIO {
class FastIOBase {
protected:
#ifdef OPENIOBUF
static const ll BUFSIZE=1<<22;
char buf[BUFSIZE+1];
ll buf_p=0;
#endif
FILE *target;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
FastIOBase(FILE *f) : target(f) {}
~FastIOBase() = default;
};
class FastOutput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
protected:
inline void __putc(char x) {
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
putc(x, target);
#endif
}
template<typename T>
inline void __write(T x) {
static char stk[64], *top;
top = stk;
if (x < 0) return __putc('-'), __write(-x);
do *(top++) = x % 10, x /= 10; while (x);
for (; top != stk; __putc(*(--top) + '0'));
}
public:
FastOutput(FILE *f = stdout) : FastIOBase(f) {}
#ifdef OPENIOBUF
inline void setTarget(FILE *f) { this->flush(),target=f; }
~FastOutput(){ flush(); }
#else
inline void setTarget(FILE *f) { target = f; }
#endif
template<typename ...T>
inline void writesp(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc(' '), 0)...}; }
template<typename ...T>
inline void writeln(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc('\n'), 0)...}; }
inline FastOutput &operator<<(char x) { return __putc(x), *this; }
inline FastOutput &operator<<(const char *s) {
for (; *s; __putc(*(s++)));
return *this;
}
inline FastOutput &operator<<(const string &s) { return (*this) << s.c_str(); }
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastOutput &operator<<(const T &x) { return __write(x), *this; }
} cout;
class FastInput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
protected:
inline char __getc() {
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
return buf[buf_p++];
#else
return getc(target);
#endif
}
public:
#ifdef OPENIOBUF
FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
FastInput(FILE *f = stdin) : FastIOBase(f) {}
inline void setTarget(FILE *f) { target = f; }
#endif
inline char getchar() { return __getc(); }
template<typename ...T>
inline void read(T &...x) { initializer_list<ll>{(this->operator>>(x), 0)...}; }
inline FastInput &operator>>(char &x) {
while (isspace(x = __getc()));
return *this;
}
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastInput &operator>>(T &x) {
static char ch, sym;
x = sym = 0;
while (isspace(ch = __getc()));
if (ch == '-') sym = 1, ch = __getc();
for (; isdigit(ch); x = (x << 1) + (x << 3) + (ch ^ 48), ch = __getc());
return sym ? x = -x : x, *this;
}
inline FastInput &operator>>(char *s) {
while (isspace(*s = __getc()));
for (; !isspace(*s) && *s && ~*s; *(++s) = __getc());
return *s = '\0', *this;
}
inline FastInput &operator>>(string &s) {
char str_buf[(1 << 8) + 1], *p = str_buf;
char *const buf_end = str_buf + (1 << 8);
while (isspace(*p = __getc()));
for (s.clear(), p++;; p = str_buf) {
for (; p != buf_end && !isspace(*p = __getc()) && *p && ~*p; p++);
*p = '\0', s.append(str_buf);
if (p != buf_end) break;
}
return *this;
}
} cin;
}
int n, m, k, a[maxn][maxn], col[maxn][maxn], cn, ans[100010];
bool p[maxn][maxn];
string c;
void dfs(ll x, ll y, ll co) {
ans[cn] += a[x][y];
col[x][y] = co;
for (ll i = 0; i < 4; i++) {
ll xc = x + dx[i], yc = y + dy[i];
if (xc < 1 || yc < 1 || xc > n || yc > m || p[xc][yc] || col[xc][yc])continue;
dfs(xc, yc, co);
}
}
signed main() {
FastIO::cin >> n >> m >> k;
for (ll i = 1; i <= n; i++) {
FastIO::cin >> c;
c = ' ' + c;
for (ll j = 1; j <= m; j++)p[i][j] = (c[j] == '*');
}
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= m; j++)
for (ll k = 0; k < 4; k++)
a[i][j] += p[i + dx[k]][j + dy[k]];
ll x, y;
while (k--) {
FastIO::cin >> x >> y;
if (!col[x][y])cn++, dfs(x, y, cn);
FastIO::cout << ans[col[x][y]] << '\n';
}
return 0;
}
```
## E. Chocolate Bar
### 题意描述
给你一块有 $n \times m$ 小块的巧克力，但是你只想吃 $k$ 小块，所以你需要切巧克力。
你只能水平或竖直的切，每一次切割的花费是所切下来若干小块的巧克力的最大边长平方。
询问最小贡献。
### 简要分析
考虑 dp。
$f_{i,j,k}$ 表示 $i \times j$ 的巧克力切割成 $k$ 小块的最小花费。
考虑递归转移，枚举横竖切那一条边。
时间复杂度 $O(nmk)$。
### 代码实现
```cpp
// LUOGU_RID: 104252173
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 7;
const ll INF = 1e9 + 7, MOD = 998244353;
inline ll read() {
char cCc;
ll xXx = 0, wWw = 1;
while (cCc < '0' || cCc > '9')
(cCc == '-') && (wWw = -wWw), cCc = getchar();
while (cCc >= '0' && cCc <= '9')
xXx = (xXx << 1) + (xXx << 3) + (cCc ^ '0'), cCc = getchar();
xXx *= wWw;
return xXx;
}
inline void write(ll xXx) {
if (xXx < 0)
putchar('-'), xXx = -xXx;
if (xXx > 9)
write(xXx / 10);
putchar(xXx % 10 + '0');
}
namespace FastIO {
class FastIOBase {
protected:
#ifdef OPENIOBUF
static const ll BUFSIZE=1<<22;
char buf[BUFSIZE+1];
ll buf_p=0;
#endif
FILE *target;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
FastIOBase(FILE *f) : target(f) {}
~FastIOBase() = default;
};
class FastOutput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
protected:
inline void __putc(char x) {
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
putc(x, target);
#endif
}
template<typename T>
inline void __write(T x) {
static char stk[64], *top;
top = stk;
if (x < 0) return __putc('-'), __write(-x);
do *(top++) = x % 10, x /= 10; while (x);
for (; top != stk; __putc(*(--top) + '0'));
}
public:
FastOutput(FILE *f = stdout) : FastIOBase(f) {}
#ifdef OPENIOBUF
inline void setTarget(FILE *f) { this->flush(),target=f; }
~FastOutput(){ flush(); }
#else
inline void setTarget(FILE *f) { target = f; }
#endif
template<typename ...T>
inline void writesp(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc(' '), 0)...}; }
template<typename ...T>
inline void writeln(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc('\n'), 0)...}; }
inline FastOutput &operator<<(char x) { return __putc(x), *this; }
inline FastOutput &operator<<(const char *s) {
for (; *s; __putc(*(s++)));
return *this;
}
inline FastOutput &operator<<(const string &s) { return (*this) << s.c_str(); }
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastOutput &operator<<(const T &x) { return __write(x), *this; }
} cout;
class FastInput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
protected:
inline char __getc() {
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
return buf[buf_p++];
#else
return getc(target);
#endif
}
public:
#ifdef OPENIOBUF
FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
FastInput(FILE *f = stdin) : FastIOBase(f) {}
inline void setTarget(FILE *f) { target = f; }
#endif
inline char getchar() { return __getc(); }
template<typename ...T>
inline void read(T &...x) { initializer_list<ll>{(this->operator>>(x), 0)...}; }
inline FastInput &operator>>(char &x) {
while (isspace(x = __getc()));
return *this;
}
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastInput &operator>>(T &x) {
static char ch, sym;
x = sym = 0;
while (isspace(ch = __getc()));
if (ch == '-') sym = 1, ch = __getc();
for (; isdigit(ch); x = (x << 1) + (x << 3) + (ch ^ 48), ch = __getc());
return sym ? x = -x : x, *this;
}
inline FastInput &operator>>(char *s) {
while (isspace(*s = __getc()));
for (; !isspace(*s) && *s && ~*s; *(++s) = __getc());
return *s = '\0', *this;
}
inline FastInput &operator>>(string &s) {
char str_buf[(1 << 8) + 1], *p = str_buf;
char *const buf_end = str_buf + (1 << 8);
while (isspace(*p = __getc()));
for (s.clear(), p++;; p = str_buf) {
for (; p != buf_end && !isspace(*p = __getc()) && *p && ~*p; p++);
*p = '\0', s.append(str_buf);
if (p != buf_end) break;
}
return *this;
}
} cin;
}
ll f[55][55][55];
ll dfs(ll n, ll m, ll p) {
if (n * m == p || p == 0)return 0;
if (n > m)swap(n, m);
if (f[n][m][p])return f[n][m][p];
ll smin = INF;
for (ll i = 1; i <= n / 2; i++)
for (ll j = 0; j <= p; j++) {
ll ans = m * m + dfs(i, m, j) + dfs(n - i, m, p - j);
smin = min(ans, smin);
}
for (ll i = 1; i <= m / 2; i++)
for (ll j = 0; j <= p; j++) {
ll ans = n * n + dfs(i, n, j) + dfs(m - i, n, p - j);
smin = min(ans, smin);
}
return f[n][m][p] = smin;
}
void solve() {
ll n, m, k;
FastIO::cin >> n >> m >> k;
FastIO::cout << dfs(n, m, k) << '\n';
}
signed main() {
// freopen("code.in", "r", stdin);
// freopen("code.out", "w", stdout);
ll T;
FastIO::cin >> T;
while (T--)solve();
return 0;
}
/*
* code by zhangzuoxiang
*/
```
## F. Cut Length
### 题意描述
给定 $n$ 个点的任意多边形，给定 $m$ 条直线求直线在多边形内部距离，在边上也算如在内。
### 简要分析
求出该直线与此多边形的所有交点，然后处在相邻两个交点间的线段便是其处于多边形内的部分。
因为 $n$ 只有 $1000$，我们完全可以枚举每一条线段来找到它与直线的交点。
很明显这些交点都在该直线上，那么我们把它们按照从直线的一段到另一端的顺序排序，然后就是找出第一个交点和第二个交点间的线段，第三个和第四个间的线段，以此类推。
这是理论上的算法。真正实现起来会发现有很多要处理的：
#### bug 1
关于重合的边的问题。
明显，如果边与直线重合，该边是一定要计入的；于是我们单独开一个数组维护所有这样的边，然后将这样的边与上文所述线段求一个并即可。
#### bug 2
关于直线何时与边有交的问题
比如说直线与一个角相交，或是直线与边重合。
在处理这 bug2 的时候，最好把所有 $180^\circ$ 的角都删掉，不然可能会增加讨论量。
最终时间复杂度 $O(nm \log n)$，因为区间并是 $O(n \log n)$ 的。
### 代码实现
```cpp
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
const ll maxn = 2e3 + 7;
const ll INF = 1e9 + 7, MOD = 998244353;
inline void write(ll xXx) {
if (xXx < 0)
putchar('-'), xXx = -xXx;
if (xXx > 9)
write(xXx / 10);
putchar(xXx % 10 + '0');
}
namespace FastIO {
class FastIOBase {
protected:
#ifdef OPENIOBUF
static const ll BUFSIZE=1<<22;
char buf[BUFSIZE+1];
ll buf_p=0;
#endif
FILE *target;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
FastIOBase(FILE *f) : target(f) {}
~FastIOBase() = default;
};
class FastOutput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
protected:
inline void __putc(char x) {
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
putc(x, target);
#endif
}
template<typename T>
inline void __write(T x) {
static char stk[64], *top;
top = stk;
if (x < 0) return __putc('-'), __write(-x);
do *(top++) = x % 10, x /= 10; while (x);
for (; top != stk; __putc(*(--top) + '0'));
}
public:
FastOutput(FILE *f = stdout) : FastIOBase(f) {}
#ifdef OPENIOBUF
inline void setTarget(FILE *f) { this->flush(),target=f; }
~FastOutput(){ flush(); }
#else
inline void setTarget(FILE *f) { target = f; }
#endif
template<typename ...T>
inline void writesp(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc(' '), 0)...}; }
template<typename ...T>
inline void writeln(const T &...x) { initializer_list<ll>{(this->operator<<(x), __putc('\n'), 0)...}; }
inline FastOutput &operator<<(char x) { return __putc(x), *this; }
inline FastOutput &operator<<(const char *s) {
for (; *s; __putc(*(s++)));
return *this;
}
inline FastOutput &operator<<(const string &s) { return (*this) << s.c_str(); }
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastOutput &operator<<(const T &x) { return __write(x), *this; }
} cout;
class FastInput : public FastIOBase {
#ifdef OPENIOBUF
public:
inline void flush()
{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
protected:
inline char __getc() {
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
return buf[buf_p++];
#else
return getc(target);
#endif
}
public:
#ifdef OPENIOBUF
FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
FastInput(FILE *f = stdin) : FastIOBase(f) {}
inline void setTarget(FILE *f) { target = f; }
#endif
inline char getchar() { return __getc(); }
template<typename ...T>
inline void read(T &...x) { initializer_list<ll>{(this->operator>>(x), 0)...}; }
inline FastInput &operator>>(char &x) {
while (isspace(x = __getc()));
return *this;
}
template<typename T, typename=typename enable_if<is_integral<T>::value>::type>
inline FastInput &operator>>(T &x) {
static char ch, sym;
x = sym = 0;
while (isspace(ch = __getc()));
if (ch == '-') sym = 1, ch = __getc();
for (; isdigit(ch); x = (x << 1) + (x << 3) + (ch ^ 48), ch = __getc());
return sym ? x = -x : x, *this;
}
inline FastInput &operator>>(char *s) {
while (isspace(*s = __getc()));
for (; !isspace(*s) && *s && ~*s; *(++s) = __getc());
return *s = '\0', *this;
}
inline FastInput &operator>>(string &s) {
char str_buf[(1 << 8) + 1], *p = str_buf;
char *const buf_end = str_buf + (1 << 8);
while (isspace(*p = __getc()));
for (s.clear(), p++;; p = str_buf) {
for (; p != buf_end && !isspace(*p = __getc()) && *p && ~*p; p++);
*p = '\0', s.append(str_buf);
if (p != buf_end) break;
}
return *this;
}
} cin;
}
template<typename T>
inline T Min(T x, T y) { return x < y ? x : y; }
template<typename T>
inline T Max(T x, T y) { return x > y ? x : y; }
template<typename T>
inline void Swap(T &x, T &y) {
T t = x;
x = y, y = t;
}
template<typename T>
inline T Abs(T x) { return x < 0 ? -x : x; }
inline ll gcd(ll a, ll b) {
return !b ? a : gcd(b, a % b);
}
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<typename T>
inline ll Pow(T n, ll k) {
if (k < 0)return 0;
T ret = 1, now = n;
while (k) {
if (k & 1)ret *= now;
now *= now, k >>= 1;
}
return ret;
}
inline ll popcount(ll n) {
ll ret = 0, u = n;
while (u)
ret += (u & 1), u >>= 1;
return ret;
}
#define for_(i, a, b) for (ll i = (a); i < (b); i++)
#define rep_(i, a, b) for (ll i = (a); i <= (b); i++)
#define fi first
#define se second
#define sz(a) a.size()
#define all(v) v.begin(), v.end()
#define pb push_back
#define DEBUG(x) cerr << #x << '=' << x << '\n'
#define ccin FastIO::cin
#define ccout FastIO::cout
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
const ldb EPS = 1e-9, pi = acos(-1);
#define double long double
const double eps = 1e-6;
ll cmp(double x) {
if (x > eps)return 1;
if (x < -eps)return -1;
return 0;
}
struct Vector {
double x, y;
Vector() {}
Vector(double X, double Y) { x = X, y = Y; }
friend Vector operator+(const Vector &u, const Vector &v) { return Vector(u.x + v.x, u.y + v.y); }
friend Vector operator-(const Vector &u, const Vector &v) { return Vector(u.x - v.x, u.y - v.y); }
friend Vector operator*(const Vector &u, const double &v) { return Vector(u.x * v, u.y * v); }
friend Vector operator/(const Vector &u, const double &v) { return Vector(u.x / v, u.y / v); }
friend double operator&(const Vector &u, const Vector &v) { return u.x * v.y - u.y * v.x; }
friend double operator|(const Vector &u, const Vector &v) { return u.x * v.x + u.y * v.y; }
double operator~() const { return sqrt(x * x + y * y); }
double operator!() const { return atan2(y, x); }
friend bool operator<(const Vector &u, const Vector &v) { return cmp(u.x - v.x) ? u.x < v.x : u.y < v.y; }
friend bool operator==(const Vector &u, const Vector &v) { return !cmp(u.x - v.x) && !cmp(u.y - v.y); }
void read() { scanf("%Lf%Lf", &x, &y); }
void prll() const { printf("(%Lf,%Lf)", x, y); }
} p[1010];
Vector read() {
Vector x;
x.read();
return x;
}
typedef Vector Poll;
struct Line {
Poll x, y;
Vector z;
Line() {}
Line(Poll X, Poll Y) { x = X, y = Y, z = Y - X; }
void prll() const { x.prll(), y.prll(); }
friend Poll operator&(const Line &u, const Line &v) { return u.x + u.z * ((v.z & (u.x - v.x)) / (u.z & v.z)); }
friend ll operator&(const Line &u, const Poll &v) {
return cmp((v - u.x) & (v - u.y));
}//poll v is on which side of line u
};
typedef Line Segment;
ll n, m;
vector<Segment> u;
vector<Poll> v, w;
vector<ll> b;
bool on[1010];
double calc(Line l) {
u.clear(), v.clear(), memset(on, false, sizeof(on));
for (ll i = 0; i < n; i++) {
if (!cmp((p[i] - p[(i + 1) % n]) & l.z)) {
if (cmp(l.z & (p[i] - l.x)))continue;
u.emplace_back(p[i], p[(i + 1) % n]);
Segment tmp(p[i], p[(i + 1) % n]);
if ((tmp & p[(i + n - 1) % n]) != (tmp & p[(i + 2) % n]))v.push_back(p[i]);
continue;
}
Poll x = Line(p[i], p[(i + 1) % n]) & l;
if (x == p[i]) {
on[i] = true;
continue;
}
if (x == p[(i + 1) % n]) {
on[(i + 1) % n] = true;
continue;
}
if (cmp((x - p[i]) | (x - p[(i + 1) % n])) == 1)continue;
v.push_back(x);
}
for (ll i = 0; i < n; i++) {
if (!on[i])continue;
if (on[(i + n - 1) % n] || on[(i + 1) % n])continue;
Poll x = (l.x == p[i] ? l.y : l.x);
Segment A(p[(i + n - 1) % n], p[i]);
bool a = ((A & x) != (A & p[(i + 1) % n]));
Segment B(p[(i + 1) % n], p[i]);
bool b = ((B & x) != (B & p[(i + n - 1) % n]));
if (a == b)v.push_back(p[i]);
}
sort(v.begin(), v.end()), w = v;
for (auto i:u)w.push_back(i.x), w.push_back(i.y);
sort(w.begin(), w.end());
b.assign(w.size(), 0);
for (ll i = 0; i < v.size(); i += 2) {
ll l = lower_bound(w.begin(), w.end(), v[i]) - w.begin();
ll r = lower_bound(w.begin(), w.end(), v[i + 1]) - w.begin();
b[l]++, b[r]--;
}
for (ll i = 0; i < u.size(); i++) {
ll l = lower_bound(w.begin(), w.end(), u[i].x) - w.begin();
ll r = lower_bound(w.begin(), w.end(), u[i].y) - w.begin();
if (l > r)swap(l, r);
b[l]++, b[r]--;
}
for (ll i = 1; i < b.size(); i++)b[i] += b[i - 1];
double ret = 0;
for (ll i = 0; i + 1 < b.size(); i++)if (b[i])ret += ~(w[i + 1] - w[i]);
return ret;
}
ll N;
signed main() {
scanf("%lld%lld", &N, &m);
for (ll i = 0; i < N; i++) {
p[n].read();
if (n >= 2 && cmp((p[n] - p[n - 1]) & (p[n] - p[n - 2])) == 0)n--, p[n] = p[n + 1];
n++;
}
if (n >= 3 && cmp((p[0] - p[n - 1]) & (p[0] - p[n - 2])) == 0)n--;
if (n >= 3 && cmp((p[1] - p[0]) & (p[1] - p[n - 1])) == 0) {
for (ll i = 0; i + 1 < n; i++)p[i] = p[i + 1];
n--;
}
while (m--)printf("%.10Lf\n", calc(Line(read(), read())));
return 0;
}
```
——$\mathscr{ClaudeZ.}