2.3 模拟赛总结
某教练疑似在放假前安排模拟赛（卡常大赛）搞人心态，好在我都卡过了。
A
$f_0=f_1=1$
$f_i$ 定义为最小的对于所有 $k(k>0,0 \leq i-2*k)$ 满足 $f_i=f_{i-k}=f_{i-k}-f_{i-2k}$ 的正整数。
求 $f_n$
爆枚即可。
tips：有人说难度不如CSP
#include <iostream>
#include <cstdio>
#include <set>
inline int read();
int f[1005];
std::set<int>se;
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
#endif
int n=read();
f[0]=f[1]=1;
for(int i=1;i<=10000;i++){
se.insert(i);
}
for(int i=2;i<=n;i++){
for(int k=1;(i-2*k)>=0;k++){
if(2*f[i-k]-f[i-2*k]<=0){
continue;
}
auto tt=se.find(2*f[i-k]-f[i-2*k]);
if(tt!=se.end()){
se.erase(tt);
}
}
f[i]=*se.begin();
for(int k=1;(i-2*k)>=0;k++){
if(2*f[i-k]-f[i-2*k]<=0){
continue;
}
auto tt=se.find(2*f[i-k]-f[i-2*k]);
if(tt==se.end()){
se.insert(2*f[i-k]-f[i-2*k]);
}
}
}
printf("%d",f[n]);
return 0;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/
B
给定一个严格升序序列 $a$ ，设最大值为 $mx$。
求出最小的正整数集合 $s$ ，使得所有的对于 $i(1 \leq i\leq |s|)$ 设$F_i=$ $\{x|x \equiv 1 \pmod{s_i}\} \cap [1,mx]$ 。
使得所有的 $F_i$ 的并集为 $a$ 。
保证有解。
从小到大枚举即可。
tips: $\mathcal{O}(\frac n 1)+\mathcal{O}(\frac n2)+\mathcal{O}( \frac n 3)+…+\mathcal{O}(\frac n n)=\mathcal{O}(n\log n)$
#include <iostream>
#include <cstdio>
#include <vector>
inline int read();
bool inseq[400005];
int del[400005];
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("lcm.in","r",stdin);
freopen("lcm.out","w",stdout);
#endif
int n=read();
if(n==1){
printf("1");
return 0;
}
int lst=0;
for(int i=1;i<=n;i++){
inseq[lst=read()]=1;
}
int ans=0;
for(int i=2;i<=lst;i++){
if(del[i]==0&&inseq[i]){
ans++;
for(int j=2;(i-1)*j+1<=lst;j++){
del[(i-1)*j+1]=1;
}
}
}
printf("%d",ans);
return 0;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
O(n/1)+O(n/2)+(O(n/3))+...+O(n/n)=O(nlogn)
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/
C
求出一张图所有节点导出子图的最大独立集大小之和，$0 \leq n \leq 26$ 。
我们可以 dfs 搜索所有的独立集然后再各种转移一下，卡卡常就过了。
tips: 只要常数小，爆踩std！
#include <iostream>
#include <cstdio>
#include <vector>
inline int read();
int del[50];
int n;
int anss;
int ans[68000005];
std::vector<int>vec[50];
void dfs(int now,int sta,int ans){
if(now==n+1){
::ans[sta]=ans;
return ;
}
dfs(now+1,sta,ans);
if(del[now]==0){
for(int j=0;j<vec[now].size();j++){
del[vec[now][j]]++;
}
dfs(now+1,sta|(1<<(now-1)),ans+1);
for(int j=0;j<vec[now].size();j++){
del[vec[now][j]]--;
}
}
return ;
}
int lowbit(int x){
return x&(-x);
}
signed main(){
#ifdef ONLINE_JUDGE
#else
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
#endif
n=read();
int m=read();
for(int i=1;i<=m;i++){
int x=read()+1;
int y=read()+1;
vec[x].push_back(y);
vec[y].push_back(x);
}
dfs(1,0,0);
for(int i=0;i<(1<<n);i++){
int tt=i;
if(ans[i]!=0){
anss+=ans[i];
continue;
}
int add=0;
while(tt>0){
int temp=lowbit(tt);
tt-=lowbit(tt);
ans[i]=std::max(ans[i],ans[tt+add]);
add+=temp;
}
anss+=ans[i];
}
printf("%d",anss);
return 0;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/
D
求出二维平面矩阵内元素和最大值。
前缀和后继续乱搞到 $\mathcal {O} (n^3)$ 。
可以发现边界一定在正的点上，于是我们的 $n$ 实际上是 $1000$ 而不是 $2000$ 。
我们继续卡常就过了。
#include <algorithm>
#include <iostream>
#include <cstdio>
inline int read();
int X[5005];
int Y[5005];
int x[1005];
int y[1005];
int x2[1005];
int y2[1005];
int map[2005][2005];
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("ex_d5.in","r",stdin);
freopen("class.out","w",stdout);
#endif
int n=read();
int nowx=0,nowy=0;
for(int i=1;i<=n;i++){
x[i]=read();
y[i]=read();
X[++nowx]=x[i];
Y[++nowy]=y[i];
}
int m=read();
for(int i=1;i<=m;i++){
x2[i]=read();
y2[i]=read();
X[++nowx]=x2[i];
Y[++nowy]=y2[i];
}
std::sort(X+1,X+nowx+1);
nowx=std::unique(X+1,X+nowx+1)-X-1;
std::sort(Y+1,Y+nowy+1);
nowy=std::unique(Y+1,Y+nowy+1)-Y-1;
for(int i=1;i<=n;i++){
x[i]=std::lower_bound(X+1,X+nowx+1,x[i])-X;
y[i]=std::lower_bound(Y+1,Y+nowy+1,y[i])-Y;
}
for(int i=1;i<=m;i++){
x2[i]=std::lower_bound(X+1,X+nowx+1,x2[i])-X;
y2[i]=std::lower_bound(Y+1,Y+nowy+1,y2[i])-Y;
}
int a=read();
int b=read();
for(int i=1;i<=n;i++){
map[y[i]][x[i]]+=a;
}
for(int i=1;i<=m;i++){
map[y2[i]][x2[i]]-=b;
}
for(int i=1;i<=nowx;i++){
for(int j=1;j<=nowy;j++){
map[j][i]+=map[j][i-1];
map[j][i]+=map[j-1][i];
map[j][i]-=map[j-1][i-1];
}
}
std::sort(x+1,x+n+1);
std::sort(y+1,y+n+1);
register int ans=0;
for(register int ii=1;ii<=n;ii++){
register int i=y[ii];
for(register int jj=ii;jj<=n;jj++){
register int j=y[jj];
register int _min=0;
for(register int kk=1;kk<=n;kk++){
register int k=x[kk];
register int sumk;
sumk=map[j][k]-map[i-1][k];
_min=std::min(_min,sumk);
ans=std::max(ans,sumk-_min);
if(kk!=1&&x[kk]-1<=x[kk-1]){
continue;
}
k=x[kk]-1;
sumk=map[j][k]-map[i-1][k];
_min=std::min(_min,sumk);
ans=std::max(ans,sumk-_min);
}
}
}
printf("%d",ans);
return 0;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/