A. ConneR and the A.R.C. Markland-N (CF 1293 A)
题目大意
(n)层楼，每层都有个餐厅，但有(k)个餐厅不开放，分别在(a_i)层，(Colin "ConneR" Neumann Jr)在第(s)层，现在他要去吃午饭，问他去餐厅最小的跨楼层是多少？
解题思路
(n)巨大但(k)很小，用(set)储存(a_i)，拿两个指针从(s)往上往下扫到没有关闭的餐厅的即可。
神奇的代码
#include <bits/stdc++.h>
#define MIN(a,b) ((((a)<(b)?(a):(b))))
#define MAX(a,b) ((((a)>(b)?(a):(b))))
#define ABS(a) ((((a)>0?(a):-(a))))
using namespace std;
typedef long long LL;
int main(void) {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int kase; cin>>kase;
for (int i = 1; i <= kase; i++) {
int n,s,k;
cin>>n>>s>>k;
set<int> qwq;
for(int u,i=1;i<=k;++i){
cin>>u;
qwq.insert(u);
}
int l=s;
int r=s;
while(true){
if (l>=1) if (qwq.find(l)!=qwq.end()) --l; else break;
if (r<=n) if (qwq.find(r)!=qwq.end()) ++r; else break;
}
int ans=0;
if (l==0) ans=r-s;
else if (r==n+1) ans=s-l;
else ans=min(s-l,r-s);
cout<<ans<<endl;
}
return 0;
}
B. JOE is on TV! (CF 1293 B)
题目大意
初始(n)个对手，答题，答错出局，某个回合，还有(s)个对手，若该回合有(t)个对手答错，则你可以获得(dfrac{t}{s}美元)。问你可能获得的最大美元数是多少？
解题思路
经过数次枚举我们可以猜想每次一个人答错，最终获得的美元数最多，以下为证明：
设当前有(t)位选手，若当前回有(s(s > 1))位选手答错，则获得的美元为(dfrac{s}{t})，由于(dfrac{1}{t-i} > dfrac{1}{t}(i geq 1))，故(sumlimits_{i=0}^{s-1}dfrac{1}{t-i} > sumlimits_{i=0}^{s-1}dfrac{1}{t}=dfrac{s}{t})，所以每次(1)位选手答错时最终所得的美元数是最大的。
神奇的代码
#include <bits/stdc++.h>
#define MIN(a,b) ((((a)<(b)?(a):(b))))
#define MAX(a,b) ((((a)>(b)?(a):(b))))
#define ABS(a) ((((a)>0?(a):-(a))))
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x) {
int s = 0, c = getchar();
x = 0;
while (isspace(c)) c = getchar();
if (c == 45) s = 1, c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s) x = -x;
}
template <typename T>
void write(T x, char c = ' ') {
int b[40], l = 0;
if (x < 0) putchar(45), x = -x;
while (x > 0) b[l++] = x % 10, x /= 10;
if (!l) putchar(48);
while (l) putchar(b[--l] | 48);
putchar(c);
}
int main(void) {
int n;
read(n);
double ans=0;
for(int i=1;i<=n;++i) ans+=1.0/(double)(n-i+1);
printf("%.6f
",ans);
return 0;
}
C. NEKO's Maze Game (CF 1293 C)
题目大意
给定一个(2*n)的矩形格子，你要从((1,1))走到((2,n))，有(q)个时刻，第(i)个时刻，((r_i,c_i))的格子的状态会翻转，即从可走变不可走，或者不可走变可走。初始所有格子可走，问每一个时刻后，你能否从((1,1))走到((2,n))。
解题思路
注意到不能达到的不可走格子分布只有两种，第一种是某一列的两个格子都不可走，第二种是相邻列的不同行格子都不可走，分别统计这两种的分布的数量，大于(0)则不可到达，否则可以到达。
神奇的代码
#include <bits/stdc++.h>
#define MIN(a,b) ((((a)<(b)?(a):(b))))
#define MAX(a,b) ((((a)>(b)?(a):(b))))
#define ABS(a) ((((a)>0?(a):-(a))))
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x) {
int s = 0, c = getchar();
x = 0;
while (isspace(c)) c = getchar();
if (c == 45) s = 1, c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s) x = -x;
}
template <typename T>
void write(T x, char c = ' ') {
int b[40], l = 0;
if (x < 0) putchar(45), x = -x;
while (x > 0) b[l++] = x % 10, x /= 10;
if (!l) putchar(48);
while (l) putchar(b[--l] | 48);
putchar(c);
}
const int N=1e5+8;
int val[2][N],cnt,n,q;
int main(void) {
read(n);
read(q);
val[0][0]=val[1][0]=val[0][n+1]=val[1][n+1]=-1;
for(int r,c,i=1;i<=q;++i){
read(r);
read(c);
r--;
val[r][c]^=1;
if (val[r][c]==1&&val[r^1][c]==1) ++cnt;
if (val[r][c]==0&&val[r^1][c]==1) --cnt;
if (val[r][c]==1&&val[r^1][c-1]==1) ++cnt;
if (val[r][c]==0&&val[r^1][c-1]==1) --cnt;
if (val[r][c]==1&&val[r^1][c+1]==1) ++cnt;
if (val[r][c]==0&&val[r^1][c+1]==1) --cnt;
if (cnt) puts("No"); else puts("Yes");
}
return 0;
}
D. Aroma's Search (CF 1293 D)
题目大意
给定一个坐标，有好多数据包，初始数据包在位置((x_0,y_0))处，之后的数据包由递推式(x_n=a_x imes x_{n-1}+b_x,y_n=a_y imes y_{n-1}+b_y)给出，第(i)个数据包编号为(i)，坐标为((x_i,y_i))。(Aroma White)的初始位置是((x_s,y_s))，它可以上下左右移动(t)次，问他最多能搜集到多少数据包。
解题思路
注意到(a_x,a_y,b_x,b_y)都大于(0)，那些数据包的坐标会越来越大，它们的距离也会越来越大，故当(Aroma White)到达某个数据包时，显然我们是往标号小的数据包去跑是最好的。第(i)个数据包和第(i-1)个数据包的曼哈顿距离为((a_x-1)*x_{i-1}+b_x+(a_y-1)*y_{i-1}+b_y)，极端情况下即是(a_x=a_y=2,b_x=b_y=0)的时候，这时候距离就是(x_{i-1}+y_{i-1})，由于(tleq 10^{16})，所以数据包的坐标我们就枚举到(10^{16})即可，由于递推式里坐标是指数级增长的，枚举到的数据包最多也就(log_2{10^{16}}approx 53)个，妥妥(O({53}^2))暴力枚举第一个到达的数据包编号贪心求数量取最大值即可。注意如果先到达第(k)个数据包，最后到了第(0)个数据包还可以继续移动的话，还要继续枚举第(k+1)个数据包及以上看能否到达。
神奇的代码
#include <bits/stdc++.h>
#define MIN(a,b) ((((a)<(b)?(a):(b))))
#define MAX(a,b) ((((a)>(b)?(a):(b))))
#define ABS(a) ((((a)>0?(a):-(a))))
using namespace std;
typedef long long LL;
const LL N=10000000000000000ll+8;
vector<pair<LL,LL>> pos;
int check(int x,LL xs,LL ys,LL t){
int cnt=0;
for(int i=x;i>=0;--i){
LL dis=abs(pos[i].first-xs)+abs(pos[i].second-ys);
if (dis<=t){
t-=dis;
xs=pos[i].first;
ys=pos[i].second;
++cnt;
}
else return cnt;
}
int len=pos.size();
for(int i=x+1;i<len;++i){
LL dis=abs(pos[i].first-xs)+abs(pos[i].second-ys);
if (dis<=t){
t-=dis;
xs=pos[i].first;
ys=pos[i].second;
++cnt;
}
else return cnt;
}
return cnt;
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
LL x0,y0,ax,ay,bx,by;
cin>>x0>>y0>>ax>>ay>>bx>>by;
LL xs,ys,t;
cin>>xs>>ys>>t;
pos.push_back(make_pair(x0,y0));
while(x0<N||y0<N){
if (x0>=ax*x0+bx) break;
x0=ax*x0+bx;
if (y0>=ay*y0+by) break;
y0=ay*y0+by;
pos.push_back(make_pair(x0,y0));
}
int ans=0;
int len=pos.size();
for(int i=0;i<len;++i)
ans=max(ans,check(i,xs,ys,t));
cout<<ans<<endl;
return 0;
}
~~第一次交MLE怀疑人生？？我就53个点怎么MLE？？后来发觉是long long溢出导致枚举数据包停不下来了~~