NOIP 55
Problem A: 军训（training）
\[【问题描述】 为了让营员收获更大, 本次秋令营增加了军训项目。军训的场地位于一片无限大的二维的台阶。定义从 (x 1, y 1) 到 (x 2, y 2) 为上了 |x 1-y 1|+ x 2-y 2| 个台阶。因为走太快了走不远, 每一次只能恰好上 k 个台阶。军训刚刚结束, 你很口渴。现在你位于 (0,0) , 请构造一种到达 (x, y) 的方案。无解输 出 -1 。 \]Solution:
\[ 一道还行的构造题。 题目大意: 一开始你在初始点 (0,0) , 每次可以跳的曼哈顿距离为 k , 输出抵达 (x, y) 跳 的最少次数并且输出方案。 首先发现 x 和 y 可正可负, 不如把 x 和 y 都取绝对值, 在之后输出时携带符号输出即 可。 因为每次的操作相当于把 k 瓜分成 x 和 y 。先考虑如果 k 是奇数那么只能拆成奇数和 偶数, 可以通过调控 k 的数量来构造答案。如果 k 是偶数 x+y 是偶数, 只要把 k 拆成两 个偶数或者奇数也是能做到的。 只有 k 是偶数并且 x+y 是奇数时无解。 设答案为 n , 在 x 轴和 y 轴上的正向移动距离为 a , 反向移动距离为 b , 那么 x+y \leq n \times k 且 (n \times k-x-y) \bmod 2=0 , 这个不好解, 但是 x 和 y 值域不大所以直接枚举 n 的值就行。 a+b=n \times k, a-b=x+y 解出 a=\frac{n \times k+x+y}{2}, b=\frac{n \times k-x-y}{2} 。那就直接考虑在前进时 的 3 个情况即可：(这里的 b 会随着逆向移动的距离而减小) b \geq k , 选择 x 和 y 里当前位置距离最终位置比较近的一个, 逆向移动 k 。 b \leq k , 选择 x 和 y 里当前位置距离最终位置比较近的一个, 逆向移动 b , 另一个移动 k-b 。 b=0 , 任意把 x 和 y 推进, 最艰难的时候过去了, 可以随便放保证了。 \]#include<bits/stdc++.h>
using namespace std ;
namespace fast_IO
{
#define FAST_IO
#define IOSIZE 100000
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef __int128_t i128;
char ibuf[IOSIZE], obuf[IOSIZE];
char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#endif//fread in OJ, stdio in local
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33&&ch!=EOF)
struct fast_IO_t{
~fast_IO_t(){
fwrite(obuf, p3-obuf, 1, stdout);
}
bool flag = false;
operator bool() {
return flag;
}
}io;
template<typename T> inline T read() {
T s = 0; int w = 1; char ch;
while(ch=getchar(), !isdigit(ch)&&(ch!=EOF))
if(ch == '-') w = -1;
if(ch == EOF) return 0;
while(isdigit(ch))
s = s*10+ch-48, ch=getchar();
if(ch == '.') {
ll flt = 0; int cnt = 0;
while(ch=getchar(), isdigit(ch))
if(cnt < 18) flt=flt*10+ch-48, cnt++;
s += (db)flt/pow(10,cnt);
}
return s *= w;
}
template<typename T> inline bool read(T &s) {
s = 0; int w = 1; char ch;
while(ch=getchar(), !isdigit(ch)&&(ch!=EOF))
if(ch == '-') w = -1;
if(ch == EOF) return false;
while(isdigit(ch))
s = s*10+ch-48, ch=getchar();
if(ch == '.') {
ll flt = 0; int cnt = 0;
while(ch=getchar(), isdigit(ch))
if(cnt < 18) flt=flt*10+ch-48, cnt++;
s += (db)flt/pow(10,cnt);
}
return s *= w, true;
}
inline bool read(char &s) {
while(s = getchar(), isspace(s));
return s != EOF;
}
inline bool read(char *s) {
char ch;
while(ch=getchar(), isspace(ch));
if(ch == EOF) return false;
while(!isspace(ch))
*s++ = ch, ch=getchar();
*s = '\000';
return true;
}
template<typename T> void print(T x) {
static int t[20]; int top = 0;
if(x < 0) putchar('-'), x = -x;
do { t[++top] = x%10; x /= 10; } while(x);
while(top) putchar(t[top--]+48);
}
struct null_type{}; int pcs = 8;
null_type setpcs(int cnt)
{
pcs = cnt;
return null_type();
}
inline void print(null_type x){}
inline void print(double x) {
if(x < 0) putchar('-'), x = -x;
x += 5.0 / pow(10,pcs+1);
print((ll)(x)); x -= (ll)(x); putchar('.');
for(int i = 1; i <= pcs; i++)
x *= 10, putchar((int)x+'0'), x -= (int)x;
}
inline void print(float x) {
if(x < 0) putchar('-'), x = -x;
x += 5.0 / pow(10,pcs+1);
print((ll)(x)); x -= (ll)(x); putchar('.');
for(int i = 1; i <= pcs; i++)
x *= 10, putchar((int)x+'0'), x -= (int)x;
}
inline void print(long double x) {
if(x < 0) putchar('-'), x = -x;
x += 5.0 / pow(10,pcs+1);
print((i128)(x)); x -= (i128)(x); putchar('.');
for(int i = 1; i <= pcs; i++)
x *= 10, putchar((int)x+'0'), x -= (int)x;
}
inline void print(char x) {
putchar(x);
}
inline void print(char *x) {
for(int i = 0; x[i]; i++)
putchar(x[i]);
}
inline void print(const char *x) {
for(int i = 0; x[i]; i++)
putchar(x[i]);
}
#ifdef _GLIBCXX_STRING//string
inline bool read(std::string& s) {
s = ""; char ch;
while(ch=getchar(), isspace(ch));
if(ch == EOF) return false;
while(!isspace(ch))
s += ch, ch = getchar();
return true;
}
inline void print(std::string x) {
for(auto i = x.begin(); i != x.end(); i++)
putchar(*i);
}
inline bool getline(fast_IO_t &io, string s)
{
s = ""; char ch = getchar();
if(ch == EOF) return false;
while(ch != '\n' and ch != EOF)
s += ch, ch = getchar();
return true;
}
#endif
template<typename T, typename... T1>
inline int read(T& a, T1&... other) {
return read(a)+read(other...);
}
template<typename T, typename... T1>
inline void print(T a, T1... other) {
print(a); print(other...);
}
template<typename T>
fast_IO_t& operator >> (fast_IO_t &io, T &b){
return io.flag=read(b), io;
}
template<typename T>
fast_IO_t& operator << (fast_IO_t &io, T b) {
return print(b), io;
}
#define cout io
#define cin io
#define endl '\n'
}
using namespace fast_IO;
#define Pair pair<int,int>
int n , k ;
Pair f(int x,int y){
if(x > y){
Pair now = f(y , x) ;
return {now.second , now.first} ;
}
if(x < 0){
Pair now = f(-x , y) ;
return {-now.first , now.second} ;
}
if(x + y >= 2 * k) return {x , y - k} ;
if(x + y == k){
return {0 , 0} ;
}
int t = (k - ((x + y) >> 1)) ;
return {-t , y - k + x + t} ;
}
stack<Pair,vector<Pair>> sta ;
int main(){
cin >> k ;
int x , y ; cin >> x >> y ;
if(k % 2 == 0 && (x + y - 1) % 2 == 0){
puts("-1") ;
return 0 ;
}
sta.emplace(x , y) ;
for( ; x || y ; x = sta.top().first , y = sta.top().second){
sta.emplace(f(x , y)) ;
}
sta.pop() ;
cout << sta.size() << endl ;
while(sta.size()){
cout << sta.top().first << " " << sta.top().second << endl ;
sta.pop() ;
}
}
ProblemB
\[【问题描述】 作为大型考试, 题目要很规范, 不能像平时的联考一样。 有 n 种需要满足的命题规范, m 个出题人, 提供 a_{i, j} 个大样例可以让第 j 个出题人满 足第 i 个规范。在找第 i 个出题人满足规范之前, 需要先提供 b_{i} 个大样例。 求满足所有命题规范最少提供多少大样例。 \]\[ 设 a_{i, p_{1}} \leq a_{i, p_{2}} \leq \cdots \leq a_{i, p_{m}} 。设最终选择的出题人集合为 S , 对于 1 \leq j \leq m , 若 \left\{p_{1}, p_{2}, \cdots, p_{j-1}\right\} \subseteq\{1,2, \cdots, m\} \backslash S , 答案会加上 a_{i, p_{j}}-a_{i, p_{j-1}} 。 \mathrm{S} 的答案即为 \{1,2, \cdots, m\} \backslash S 所有子集的贡献之和。做一个 SOS DP 即可。 时间复杂度为 O\left(n m \log m+m 2^{m}\right) 。 \]Problem C: 前置知识（knowledge）
\[【问题描述】 给定两个序列 a_{1}, a_{2}, \cdots, a_{n} 和 b_{1}, b_{2}, \cdots, b_{n} 。 求一个 1,2, \cdots, n 的排列 \left\{c_{n}\right\} , 最小化: \sum_{i=1}^{n}\left\lceil\frac{\max \left(a_{i}-b_{c_{i}}, 0\right)}{k}\right\rceil \]1669818063
1239130100
2061579057
1196779366
2899309225