T1
欧拉筛质数时若 \(i\) 是质数且没有被用过就顺便用于计算结果，复杂度 \(O(n)\)
#include<bits/stdc++.h>
using namespace std;
inline int Rd() {
register int x=0; char C=getchar();
for(;C<'0'||C>'9';C=getchar()) ;
for(;C>'/'&&C<':';C=getchar()) x=(x<<1)+(x<<3)+(C^48);
return x;
}
const int N=10000000;
int is[N+5],pr[664585],cnt,sm[N+5],vs[N+5],L,R,T;
inline void Out(int x) {
if(x>9)Out(x/10);
putchar(x%10|48);
}
int main() {
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
is[1]=1;
for(register int i=2;i<=N;i++) {
if(!is[i])pr[++cnt]=i,++sm[i];
for(register int j=1;j<=cnt && i*pr[j]<=N;j++) {
is[i*pr[j]]=1;
if(!is[i] && !vs[i*pr[j]])
++sm[i*pr[j]],vs[i*pr[j]]=1;
if(i%pr[j]==0)break;
}
}
for(register int i=1;i<=N;i++)sm[i]+=sm[i-1];
T=Rd();
while(T--) {
L=Rd(),R=Rd();
Out(sm[R]-sm[L-1]);
putchar(10);
}
}
T2
考试时没有想到贪心做法，炸了。。
正解：一条线两边站企鹅这种情况越多越好，可以直接求出这样连的边数，剩下的企鹅肯定直接与已知的相连即可
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int T,n,K,ans,use,lst[N],nxt[N<<1],to[N<<1],vis[N],cnt;
inline void Ae(int fr,int go) {
to[++cnt]=go,nxt[cnt]=lst[fr],lst[fr]=cnt;
}
void dfs(int u,int f) {
for(int i=lst[u],v;i;i=nxt[i])
if((v=to[i])^f) {
dfs(v,u);
if(!vis[u] && !vis[v]) {
if(use<K)++ans;
use+=2;
vis[u]=vis[v]=1;
}
}
}
int main() {
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&K);
memset(lst,0,sizeof(lst));
memset(vis,0,sizeof(vis));
cnt=0;
for(int i=1,x;i<n;i++) {
scanf("%d",&x);
Ae(i+1,x),Ae(x,i+1);
}
ans=use=0;
dfs(1,1);
if(use<K)ans+=K-use;
printf("%d\n",ans);
}
}
T3
容易看出是状压再跑一遍走迷宫一样的玩意。
不知道为什么打了一个 \(\text{SPFA}\) ，蜜汁 95 分，感觉还是用普通广搜稳重。
希望下次注意
#include<bits/stdc++.h>
using namespace std;
const int N=5005,M=6005;
int n,m,K,p[30]={1},gt[N],nxt[M],to[M],lst[N],st[M],vis[N][1025];
struct ps {
int u,s,p;
ps(int x=0,int y=0,int z=0):
u(x),s(y),p(z) { }
}nw;
queue<ps>q;
int main() {
freopen("room.in","r",stdin);
freopen("room.out","w",stdout);
for(int i=1;i<=20;i++)p[i]=p[i-1]<<1;
scanf("%d%d%d",&n,&m,&K);
for(int i=1,x;i<=n;i++) {
for(int j=1;j<=K;j++) {
scanf("%d",&x);
if(x)gt[i]|=p[j-1];
}
}
for(int i=1,fr,x;i<=m;i++) {
scanf("%d%d",&fr,&to[i]);
for(int j=1;j<=K;j++) {
scanf("%d",&x);
if(x)st[i]|=p[j-1];
}
nxt[i]=lst[fr],lst[fr]=i;
}
q.push(ps(1,gt[1],0));
vis[1][gt[1]]=1;
while(!q.empty()) {
nw=q.front(),q.pop();
register int u=nw.u,ns=nw.s;
for(int i=lst[u],v,vs;i;i=nxt[i])
if((ns&st[i])==st[i]) {
if(!vis[v=to[i]][vs=ns|gt[v]]) {
q.push(ps(v,vs,nw.p+1));
vis[v][vs]=1;
if(v==n) {
printf("%d",nw.p+1);
return 0;
}
}
}
}
printf("No Solution");
}
T4
比赛时用链表暴力整了一个 60 。但正如 PMX 所说：这已经是正解了
题目可以转化为找到最近一个符合条件的位置，用线段树就可以维护了
\(P.S.\) 权值线段树更加方便
#include<bits/stdc++.h>
using namespace std;
inline int Rd() {
register int x=0; char C=getchar();
for(;C<'0'||C>'9';C=getchar()) ;
for(;C>'/'&&C<':';C=getchar()) x=(x<<1)+(x<<3)+(C^48);
return x;
}
inline void Out(int x) {
if(x>9)Out(x/10);
putchar(x%10|48);
}
const int N=100005;
int n,mx,x[N],y[N],ans[N],sz[N<<2];
void Sort(int l,int r) {
int i=l,j=r,mid=x[rand()%(r-l)+l];
while(i<=j) {
while(x[i]<mid)i++;
while(x[j]>mid)j--;
if(i<=j) {
swap(x[i],x[j]);
swap(y[i],y[j]);
i++,j--;
}
}
if(i<r)Sort(i,r);
if(j>l)Sort(l,j);
}
void build(int l,int r,int rt) {
if(l==r) { sz[rt]=1; return; }
register int mid=l+r>>1;
build(l,mid,rt<<1),build(mid+1,r,rt<<1|1);
sz[rt]=sz[rt<<1]+sz[rt<<1|1];
}
int ask(int k,int l,int r,int rt) {
if(l==r)return k>1?-1:l;
register int mid=l+r>>1;
if(sz[rt<<1]>=k)return ask(k,l,mid,rt<<1);
else return ask(k-sz[rt<<1],mid+1,r,rt<<1|1);
}
void change(int p,int l,int r,int rt) {
--sz[rt];
if(l==r)return;
register int mid=l+r>>1;
if(p<=mid)change(p,l,mid,rt<<1);
else change(p,mid+1,r,rt<<1|1);
}
int main() {
freopen("queue.in","r",stdin);
freopen("queue.out","w",stdout);
n=Rd();
for(int i=1;i<=n;i++)
x[i]=Rd(),y[i]=Rd();
build(1,n,1);
if(n>1)Sort(1,n);
for(int i=1;i<=n;i++)
if(n-i<y[i])
return printf("impossible"),0;
for(int i=1,p,q;i<=n;i++) {
p=ask(y[i]+1,1,n,1);
q=ask(n-y[i]-i+1,1,n,1);
if(p<=q)ans[p]=x[i],change(p,1,n,1);
else ans[q]=x[i],change(q,1,n,1);
}
for(int i=1;i<=n;i++)
Out(ans[i]),putchar(32);
}