赛时rank13，T1 100,T2 10,T3 57,T4 0
花间叔祖
水题。考虑答案可能为1或2。假设所有的数都可以表示为\(am+1\)，那么答案就是1，反之为0。
将差求gcd，若为1，则答案为2，反之为1.
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define CAI int
#define cai long long
#define CAi cin
#define CaI cout
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
const CAI N = 2e5 + 10;
CAI n,a[N];
signed main(){
CAi.tie(nullptr)->sync_with_stdio(false);
CaI.tie(nullptr)->sync_with_stdio(false);
CAi>>n;
for(CAI i = 1;i <= n; ++i) CAi>>a[i];
sort(a+1,a+1+n);
CAI gcd = 0;
for(CAI i = 2;i <= n; ++i) gcd = __gcd(gcd,a[i]-a[i-1]);
if(gcd > 1) CaI<<1;
else{
unordered_set<CAI> p;
for(CAI i = 1;i <= n; ++i) p.insert(a[i]%2);
CaI<<p.size();
}
}
合并r
设\(f_{i,j}\)表示已经用了\(i\)个数，凑出的和为\(j\)
有
\[f_{i,j} = f_{i-1,j-1} + f{i,j*2} \]答案为\(f_{n,k}\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
const int mod = 998244353,N = 5010;
int n,k,f[N][N];
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>k;
if(n == 1) return cout<<1,0;
f[0][0] = 1;
for(int i = 1;i <= n; ++i)
for(int j = i;j >= 1; --j)
f[i][j] = (f[i-1][j-1] + f[i][j*2]) % mod;
cout<<f[n][k]<<'\n';
}
回收波特
考虑将所有点的移动转化为原点的移动。发现数据结构无法维护。but值域很小，可以利用这个性质。
我们发现，关于原点对称的两个点的移动一定是对称的。所以可以将两个点并在一起。
就做完了。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
const int N = 1e6 + 10;
int n,m,l,r,tag,x[N],stop[N],pos[N];
bitset<N> vis;
struct EDGE{int to,next;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v){
edge[++cnt] = {v,head[u]};
head[u] = cnt;
}
void dfs(int x){
vis[x] = true;
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;
if(vis[y]) continue;
if(stop[x]) stop[y] = stop[x];
else pos[y] = -pos[x];
dfs(y);
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>m;
l = 1,r = N-10;
for(int i = 1;i <= n; ++i) cin>>x[i];
for(int i = 1,d;i <= m; ++i){
cin>>d;
if(l + tag > 0) tag -= d;
else tag += d;
int mid = -tag;
if(l <= mid && mid <= r){
stop[mid] = i;
if(2*mid < l+r){
for(int j = l;j < mid; ++j) add(mid*2-j,j);
l = mid + 1;
}
else{
for(int j = r;j > mid; --j) add(mid*2-j,j);
r = mid-1;
}
}
}
for(int i = l;i <= r; ++i){
if(!stop[i]) pos[i] = i + tag;
dfs(i);
}
for(int i = 1;i < l; ++i) if(stop[i]) dfs(i);
for(int i = N-10;i > r; --i ) if(stop[i]) dfs(i);
for(int i = 1;i <= n; ++i){
if(stop[x[i]]) cout<<"Yes "<<stop[x[i]]<<'\n';
else cout<<"No "<<pos[x[i]]<<'\n';
}
}
斗篷
神奇题，我不会，跳了。
标签：freopen,int,提高,long,FILE,using,csp,模拟,define From： https://www.cnblogs.com/hzoi-Cu/p/18319661