2020ICPC·小米 网络选拔赛第一场（2020.10.25）
队伍名称：代码养生学
A.Intelligent Waregouse
有(n)个数，从中选出一些数，要求这些数里每一对一个是另一个的倍数
(1leq nleq 2 imes10^{5},1leq a_{i} leq 10^{7})
题解：
按(a_i)从小到大dp，枚举每个(a_{i})的约数（(10^{7})内约数最多的个数只有448个）
枚举约数的方法可以质因数分解枚举每个质因数的指数然后进行dfs
代码：zsy
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=1e7+5;
int n,zhi[M],pri[M],tot,d[M],a[200005],mx,now,chk[M],dp[M];
void dfs(int y,int z){
if(y==1){
if(z!=now)
mx=max(mx,dp[z]);
return;
}
int p=d[y],q=0;
while(y%p==0)++q,y/=p;
for(int i=0;i<=q;++i)
dfs(y,z),z*=p;
}
int main(){
scanf("%d",&n);
for(int i=2;i<M;++i){
if(!zhi[i])
pri[++tot]=i,d[i]=i;
for(int j=1;i*pri[j]<M;++j){
zhi[i*pri[j]]=1;
d[i*pri[j]]=pri[j];
if(i%pri[j]==0)break;
}
}
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
++dp[a[i]];
}
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<=n;++i){
if(!chk[a[i]]){
mx=0,now=a[i],dfs(a[i],1),dp[a[i]]+=mx;
chk[a[i]]=1;
}
ans=max(ans,dp[a[i]]);
}
printf("%d
",ans);
return 0;
}
B.Intelligent Robot
给出一个方格从((0,0))到((n,m))，然后给出(k)个墙，给出起点终点然后计算两个点不穿过墙的最短路
(1 leq n,m leq 10^4,1leq kleq 300)
给出的数字都是整数
题解：
拿出墙的两个端点和起点终点，把能直接走到的点连边求最短路
代码：zsy
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int N=1005;
struct node{
int x,y;
}p[N];
struct line{
int x1,y1,x2,y2;
void print(){
printf("(%d,%d) -- (%d,%d) ",x1,y1,x2,y2);
}
}l[N];
int n,m,k,sx,sy,tx,ty,vis[N];
double dis[N];
vector<int>E[N];
bool _inter(line a,line b){
if(max(a.x1,a.x2)<min(b.x1,b.x2))return false;
if(max(a.y1,a.y2)<min(b.y1,b.y2))return false;
int k1 = (a.x2 - a.x1)*(b.y1 - a.y1) - (b.x1 - a.x1)*(a.y2 - a.y1);
int k2 = (a.x2 - a.x1)*(b.y2 - a.y1) - (b.x2 - a.x1)*(a.y2 - a.y1);
if((long long)k1 * k2 <= 0){
return true;
}
else{
return false;
}
}
bool inter(line a,line b){
// printf("inter ");
// a.print();
// b.print();
// puts("");
bool res=_inter(a,b)&&_inter(b,a);
// printf("res = %d
",res);
return res;
}
double sqr(double x){
return x*x;
}
double calc(int i,int j){
return sqrt(sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y));
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=0,a,b,c,d;i<k;++i){
scanf("%d%d%d%d",&a,&b,&c,&d);
l[i] = (line){a,b,c,d};
p[i+i]=(node){a,b};
p[i+i+1]=(node){c,d};
}
scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
p[k+k]=(node){sx,sy};
p[k+k+1]=(node){tx,ty};
for(int i=0;i<k+k+2;++i){
if(i<k+k)
E[i].push_back(i^1);
for(int j=i+1;j<k+k+2;++j)
if((i>>1)==k||(j>>1)==k||(i>>1)!=(j>>1)){
int fg=1;
for(int o=0;o<k;++o)
if(o!=(i>>1)&&o!=(j>>1))
if(inter((line){p[i].x,p[i].y,p[j].x,p[j].y},l[o])){
fg=0;break;
}
if(fg){
// printf("i=%d j=%d ok
",i,j);
E[i].push_back(j),E[j].push_back(i);
}
}
}
for(int i=0;i<=k+k+2;++i)
dis[i]=1e30;
dis[k+k]=0;
for(int t=1;t<=k+k+2;++t){
int p=k+k+2;
for(int i=0;i<k+k+2;++i)
if(!vis[i]&&dis[i]<dis[p])
p=i;
// printf("p = %d, dis = %.4lf
",p,dis[p]);
vis[p]=1;
for(int i:E[p])
if(!vis[i])
dis[i]=min(dis[i],dis[p]+calc(i,p));
}
printf("%.4lf
",dis[k+k+1]);
return 0;
}
C.Smart Browser
水题，略过了
代码：zsy
#include<cstdio>
#include<cstring>
char str[100005];
int n,ans;
int main(){
scanf("%s",str);
n=strlen(str);
for(int i=0,j=0;i<n;i=j=j+1)
if(str[i]=='w'){
while(j+1<n&&str[j+1]=='w')++j;
ans += 2*(j-i)+1;
}
printf("%d
",ans);return 0;
}
D.Router Mesh
给一张(n)个点(m)条边的图，求去掉一个点后图中连通块的个数
(1leq n,m leq 3 imes10^{5})
题解：
求割点，每个点能构成的连通块的个数是儿子中(low[v] >= dfn[u])的个数+1，特判一下最高点
代码：zsy
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=3e5+5;
int n,m,dfn[N],low[N],tim,ans[N];
vector<int>E[N];
struct UUUUFS{
int fa[N],cnt;
void init(){
for(int i=1;i<=n;++i)fa[i]=i;
cnt=n;
}
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void link(int x,int y){
if(find(x)!=find(y))
--cnt,fa[find(x)]=find(y);
}
}ufs;
void Tarjan(int u,int f){
dfn[u]=low[u]=++tim;
int son=0;
for(int v:E[u])
if(v!=f)
if(!dfn[v]){
++son;
Tarjan(v,u);
low[u]=min(low[u],low[v]);
if(u!=f&&low[v]>=dfn[u])
++ans[u];
}
else low[u]=min(low[u],dfn[v]);
if(u==f)ans[u]=son-1;
}
int main(){
scanf("%d%d",&n,&m);
ufs.init();
for(int i=1,x,y;i<=m;++i){
scanf("%d%d",&x,&y);
E[x].push_back(y);
E[y].push_back(x);
ufs.link(x,y);
}
for(int i=1;i<=n;++i)
if(!dfn[i])
Tarjan(i,i);
for(int i=1;i<=n;++i)
printf("%d%c",ufs.cnt + ans[i],i==n?'
':' ');
return 0;
}
E.Phone Network
给出序列(a_{1},a_{2}..a_{n})，(1leq a_{i} leq m)，求(l_{i})表示(1-i)都出现的最短序列长度
(1leq m leq n leq 2 imes 10^{5})，保证(m)个数都出现过
题解：
这个问题可以转化成，对于(l_{i})，两个相同(1,2,3...i)之间的区间，不能同时包含我的左右区间端点
这样就对每个左端点有了右端点的最小限制，每个左端点要取前缀max，所以每个时刻这个右端点是单调不降的
每次做的更新相当于一次区间覆盖，维护减下标取最小值也很简单就可以实现了
代码：sjq
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
//#define ivorysi
#define enter putchar('
')
#define space putchar(' ')
#define pb push_back
#define pii pair<int,int>
#define MAXN 200005
typedef long long int64;
using namespace std;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
int N,M,a[MAXN],last[MAXN],r[MAXN];
vector<int> cnt[MAXN];
struct node {
int l,r;
int maxv,cov,minq;
}tr[MAXN * 10];
void addcover(int u,int c) {
tr[u].cov = c;
tr[u].maxv = c;
tr[u].minq = c - tr[u].r + 1;
}
void pushdown(int u) {
if(tr[u].cov != -1) {
addcover(u << 1,tr[u].cov);
addcover(u << 1 | 1,tr[u].cov);
tr[u].cov = -1;
}
}
void update(int u) {
tr[u].maxv = max(tr[u << 1].maxv,tr[u << 1 | 1].maxv);
tr[u].minq = min(tr[u << 1].minq,tr[u << 1 | 1].minq);
}
void build(int u,int l,int r) {
tr[u].l = l;tr[u].r = r;
tr[u].cov = -1;
if(l == r) {
tr[u].maxv = l;tr[u].minq = 1;
return;
}
int mid = (l + r) >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
update(u);
}
int querymax(int u,int l,int r) {
if(tr[u].l == l && tr[u].r == r) {
return tr[u].maxv;
}
int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u);
if(r <= mid) return querymax(u << 1,l,r);
else if(l > mid) return querymax(u << 1 |1,l,r);
else {
return max(querymax(u << 1,l,mid),querymax(u << 1 |1,mid +1,r));
}
}
int query(int u,int l,int r,int pos) {
if(l == r) {
if(tr[u].maxv >= pos) return l;
else return l + 1;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(r <= mid) return query(u << 1,l,r,pos);
else if(l > mid) return query(u << 1 | 1,l,r,pos);
else {
int mv = querymax(u,l,mid);
if(mv >= pos) return query(u << 1,l,mid,pos);
else return query(u << 1 | 1,mid + 1,r,pos);
}
}
void trcover(int u,int l,int r,int v) {
if(l > r) return;
if(tr[u].l == l && tr[u].r == r) {
addcover(u,v);
return;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(r <= mid) trcover(u << 1,l,r,v);
else if(l > mid) trcover(u << 1 | 1,l,r,v);
else {trcover(u << 1,l,mid,v);trcover(u << 1 | 1,mid +1,r,v);}
update(u);
}
void Init() {
read(N);read(M);
for(int i = 1 ; i <= N ; ++i) read(a[i]);
for(int i = N ; i >= 1 ; --i) {
if(last[a[i]]) {
r[i + 1] = last[a[i]];
}
else {
r[i + 1] = 1e7;
}
r[i] = max(r[i],i);
cnt[a[i]].pb(i);
last[a[i]] = i;
}
build(1,1,N);
}
void Solve() {
for(int i = 1 ; i <= M ; ++i) {
for(int j = 0 ; j < cnt[i].size() ; ++j) {
int t = cnt[i][j];
if(t + 1 <= N) {
int cr = query(1,t + 1,min(r[t + 1],N),r[t + 1]);
trcover(1,t + 1,cr - 1,r[t + 1]);
}
}
int cr = query(1,1,last[i],last[i]);
trcover(1,1,cr - 1,last[i]);
out(tr[1].minq);
i == M ? enter : space;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}
F.Design Problemset
有(k)种题，要组建题库，每个题库题目必须在([L,R])之间，每个题库中每种题必须在(l_{i},r_{i})之间
(1leq k leq 10^5,1leq L leq R leq 10^{9})
(1leq a_{i} leq 10^{9})
题解：
累加先判断下界总和超过R和上界总和不足L
之后二分答案，先把每个题的下界填满，此时若下界超过L，那么直接判断即可
若二分答案是mid，第(i)种题剩下的是(rem_{i})
先给每个题库多加(min{lfloor frac{rem_{i}}{mid} floor,r_{i} - l_{i} })
如果有类型的题还有空位，还有剩下的题，只要把这些剩下的加起来和不够的总数比较一下即可，如果够用则一定存在一种方案使得二分的答案成立
代码：sjq
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
//#define ivorysi
#define enter putchar('
')
#define space putchar(' ')
#define pii pair<int,int>
#define MAXN 100005
typedef long long int64;
using namespace std;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
int k;
int64 L,R,a[MAXN],l[MAXN],r[MAXN],sum,lsum,rsum,rem[MAXN],ad[MAXN];
bool check(int64 mid) {
for(int i = 1 ; i <= k ; ++i) {
if(l[i] * mid > a[i]) return false;
rem[i] = a[i] - l[i] * mid;
}
int64 t = L - lsum;
if(t <= 0) return true;
for(int i = 1 ; i <= k ; ++i) {
ad[i] = r[i] - l[i];
int64 c;
if(mid * ad[i] <= rem[i]) {
c = ad[i];
}
else {
c = rem[i] / mid;
}
rem[i] -= mid *c;
ad[i] -= c;
t -= c;
}
if(t <= 0) return true;
int64 s = 0;
for(int i = 1 ; i <= k ; ++i) {
if(ad[i] && rem[i]) s += rem[i];
}
return s >= t * mid;
}
void Solve() {
read(k);read(L);read(R);
for(int i = 1 ; i <= k ; ++i) {
read(a[i]);
sum += a[i];
}
for(int i = 1 ; i <= k ; ++i) {
read(l[i]);read(r[i]);
lsum += l[i];
rsum += r[i];
}
if(rsum < L || lsum > R) {
puts("0");return;
}
L = max(L,lsum);
int64 al = 0,ar = sum / L;
while(al < ar) {
int64 mid = (al + ar + 1) >> 1;
if(check(mid)) al = mid;
else ar = mid - 1;
}
out(al);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
G.Tree Projection
给出树的一个拓扑序(A)和一个dfs序(B)，构造一棵树满足这两个序列
题解：
设(i)在(A)序列的位置为(V_{i})
我们对每个(V_{B_{i}})统计前缀最小值，把前缀最小值串成一个链，B中两个前缀最小值之间的点连到靠前的前缀最小值上，形成一个菊花，可以发现满足A和B
代码：ljh
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int A[MAXN + 1], B[MAXN + 1], PosB[MAXN + 1];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &B[i]);
PosB[B[i]] = i;
}
for (int i = 1; i <= n; i++)
scanf("%d", &A[i]);
int p = A[1];
puts("YES");
for (int i = 2; i <= n; i++)
{
printf("%d %d
", p, A[i]);
if (PosB[A[i]] < PosB[p])
p = A[i];
}
return 0;
}
H.Grouping
有(2n)个数，求所有两两分组方案数，每组绝对值的方差的期望
方差可以认为是(E((x - E(x))^{2}))，根据期望的线性性，可以得到(D(x) = E(x^{2}) - E^{2}(x))
那么我们要求的就是(E(D(x)) = E(E(x^{2})) - E(E^{2}(x)))
前者是对所有数对平方和在每种划分的出现次数的计数，再乘上(frac{1}{n(2n-1)!!})
考虑((a - b)^2 = a^{2} - 2ab + b^{2})，只需要考虑单个数字平方和还有两个不同的数相乘的总和
其中(n!! = n(n - 2)(n - 4)...1)，n是奇数
后者考虑平方和转有序对，相当于枚举两个数对，其绝对值相乘，再统计在几个方案里出现过，然后累加
考虑容斥，我们把计算分成四种，(ans_{4})是这两个数对有4个不同的数的总和，(ans_{3})是这两个数有3个不同的数的总和（3，4）都是有序数对相乘，(ans_{2})是两个数对有2个不同的数的总和，我们要计算的就是(frac{1}{n^{2}(2n-1)!!}(ans_{4}(2n-5)!! + ans_{2}(2n - 3)!!))
(ans_{2})和第一个问题一样
设所有数对两两相乘总和为(s)，那么(ans_{4} = s - ans_{2} - ans_{3})
(ans_3)可以通过枚举两个数对的相同点，计算都包含某一个点的数对平方和，设为(t)
(ans_{3} = t - 2 imes ans_{2})
之后问题就可以解决了
代码：zsy+ljh
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+5;
const int mod=998244353;
int n,a[N],pre[N],suf[N];
void Inc(int &x,int y){
x=x+y>=mod?x+y-mod:x+y;
}
int mul(int x,int y){
return 1ll*x*y%mod;
}
int fastpow(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n+n;++i)scanf("%d",&a[i]);
if(n==1){
puts("0");
return 0;
}
int djc_1 = 1, djc_2 = 1;
for(int i=1;i<=n+n-3;i+=2)
djc_1 = mul(djc_1, i);
for(int i=1;i<=n+n-5;i+=2)
djc_2 = mul(djc_2, i);
sort(a+1,a+n+n+1);
int ans1 = 0;
for(int i=1,sum=0;i<=n+n;++i){
Inc(ans1, mul(n+n-1, mul(a[i], a[i])));
Inc(ans1, mul(mod-2, mul(sum, a[i])));
Inc(sum, a[i]);
}
int ans21 = 0, ans22 = 0, ans23 = 0;
for(int i=1;i<=n+n;++i)
Inc(ans21, mul(i+i-n-n-1+mod, a[i]));
ans21 = mul(ans21, ans21);
ans22 = ans1;
for(int i=1;i<=n+n;++i)
pre[i]=(pre[i-1]+a[i])%mod;
for(int i=n+n;i;--i)
suf[i]=(suf[i+1]+a[i])%mod;
for (int i=1;i<=n+n;++i){
int tmp=mul(a[i], i+i-n-n-1+mod);
Inc(tmp, suf[i+1]);
Inc(tmp, mod-pre[i-1]);
Inc(ans23, mul(tmp, tmp));
}
// printf("ans21 = %d , ans22 = %d, ans23 = %d
",ans21,ans22,ans23);
int ans2 =( (ans21 + ans22)%mod + mod - ans23)%mod;
ans1 = mul(ans1, djc_1);
ans2 = mul(ans2, djc_2);
// printf("ans1 = %d, ans2 = %d
",ans1, ans2);
Inc(ans2, ans1);
int ans = (mul(n, mul(n, ans1)) - mul(n, ans2) + mod)%mod;
// printf("%d
",ans);
for(int i=1;i<=n+n;i+=2)
ans = mul(ans, fastpow(i,mod-2));
ans = mul(ans, fastpow(n,mod-4));
printf("%d
",ans);
return 0;
}
代码：sjq（赛后的一个实现，s2,s3,s4和题解里对应值相同）
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
//s#define ivorysi
#define enter putchar('
')
#define space putchar(' ')
#define pb push_back
#define pii pair<int,int>
#define MAXN 100005
typedef long long int64;
using namespace std;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
const int MOD = 998244353;
int N;
int a[MAXN * 2],sum[MAXN * 2],f[MAXN * 2];
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
int fpow(int x,int c) {
int t = x,res = 1;
while(c) {
if(c & 1) res = mul(res,t);
t = mul(t,t);
c >>= 1;
}
return res;
}
void update(int &x,int y) {
x = inc(x,y);
}
void Init() {
read(N);
for(int i = 1 ; i <= 2 * N ; ++i) {
read(a[i]);
}
sort(a + 1,a + 2 * N + 1);
for(int i = 1 ; i <= 2 * N ; ++i) {
sum[i] = inc(sum[i - 1],a[i]);
}
f[1] = 1;
for(int i = 3 ; i <= 2 * N - 1 ; ++i) f[i] = mul(f[i - 2],i);
}
int Calc() {
int s1 = 0;
for(int i = 1 ; i <= 2 * N ; ++i) {
update(s1,mul(2 * N - 1,mul(a[i],a[i])));
update(s1,MOD - mul(2,mul(a[i],sum[i - 1])));
}
return s1;
}
int Solve1() {
int res = Calc();
if(N > 1) res = mul(res, f[2 * N - 3]);
res = mul(res,fpow(N,MOD - 2));
return res;
}
int Solve2() {
int s4 = 0;
for(int i = 2 ; i <= 2 * N ; ++i) {
update(s4,inc(mul(i - 1,a[i]),MOD - sum[i - 1]));
}
s4 = mul(s4,s4);
int s2 = Calc();
int s3 = 0;
for(int i = 1 ; i <= 2 * N ; ++i) {
int t0 = inc(mul(i - 1,a[i]),MOD - sum[i - 1]);
int t1 = inc(inc(sum[2 * N],MOD - sum[i]),MOD - mul(2 * N - i,a[i]));
//out(t0);space;out(t1);enter;
int t = inc(t0,t1);
update(s3,mul(t,t));
}
update(s3,MOD - mul(2,s2));
update(s4,MOD - inc(s2,s3));
int res = 0;
if(N > 1) s2 = mul(s2,f[2 * N - 3]);
if(N > 2) s4 = mul(s4,f[2 * N - 5]);
update(res,inc(s2,s4));
res = mul(res,fpow(mul(N,N),MOD - 2));
return res;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
int ans1 = Solve1(),ans2 = Solve2();
int ans = inc(ans1,MOD - ans2);
ans = mul(ans,fpow(f[2 * N - 1],MOD - 2));
out(ans);enter;
}
I.Walking Machine
有一个(n imes m)的矩阵，每个点有移动方向，求会走出去的点的个数
题解：
模拟就行，不说了
代码：ljh
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
int n, m, F[MAXN][MAXN + 1];
char S[MAXN][MAXN + 1];
int f(int i, int j)
{
if (i < 0 || i >= n || j < 0 || j >= m)
return 1;
if (F[i][j] == -1)
{
F[i][j] = 0;
int x = i, y = j;
switch (S[i][j])
{
case 'W': x--; break;
case 'A': y--; break;
case 'S': x++; break;
case 'D': y++; break;
}
F[i][j] = f(x, y);
}
return F[i][j];
}
int main()
{
int ans = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
scanf("%s", S[i]);
memset(F[i], -1, sizeof(int[m]));
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (f(i, j))
ans++;
printf("%d
", ans);
return 0;
}
J.Matrix Subtraction
给一个(n imes m)的矩阵，每次可以选一个(a imes b)个矩形减去1，问能不能减成全0
题解：
由于((1,1))存在的话肯定要被减去，那么就从前往后枚举有值的地方一直减就行
代码：ljh
#include <bits/stdc++.h>
using namespace std;
typedef long long big;
const int MAXN = 1000, MAXM = 1000;
int A[MAXN + 1][MAXM + 1];
big S[MAXN + 1][MAXN + 1];
int main()
{
int kase;
scanf("%d", &kase);
while (kase--)
{
int n, m, a, b;
scanf("%d%d%d%d", &n, &m, &a, &b);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
scanf("%d", &A[i][j]);
S[i][j] = 0;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
S[i][j] = S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1];
int x = max(0, i - a), y = max(0, j - b);
big v = S[i][j] - S[i][y] - S[x][j] + S[x][y];
if (v > A[i][j])
goto fail;
A[i][j] -= v;
if (A[i][j])
{
if (i + a - 1 <= n && j + b - 1 <= m)
S[i][j] += A[i][j];
else
goto fail;
}
}
puts("^_^");
continue;
fail:
puts("QAQ");
}
return 0;
}
K.Sqrt Approaching
给出(A,B,n)，保证(n)不是完全平方数
若(frac{A}{B} < sqrt{n})，求$C,D (使得)frac{A}{B} < frac{C}{D} < sqrt{n}$
若(frac{A}{B} > sqrt{n})，求(C,D)使得(frac{A}{B} > frac{C}{D} > sqrt{n})
题解：
ljh同学当即翻开了数分，找到了一个收敛于(sqrt{n})的数列，也就是
(a_{n +1} = a_{n} + frac{n}{a_{n}})
我们代入(frac{A}{B})，可以得到(frac{A}{B} + frac{nB}{A})，为了方便我们取(frac{A + nB}{A + B})，可以知道这也是往(sqrt{n})收敛的，但是大小不固定，然后结果迭代两次就落在区间里了
大整数加法用python实现的
代码：ljh
a = int(input())
b = int(input())
n = int(input())
a, b = a + n * b, a + b
a, b = a + n * b, a + b
print(a)
print(b)