|
正解：二分图匹配
考场上想都没想打了贪心
本以为会爆0，神奇的A了，惊了
（二分图只练了模板，这么明显的题目竟然没想到 //3y7h贪心写炸了
//惊了乱搞居然A了可能数据太水了吧
//正解二分图
#include<bits/stdc .h>
using namespace std;
const int INF=1e9 9;
int n,b[2019],num,an[50][50],res=0;
bool v[2019],s[50][50],prime[2019],ans[2019],use[50];
struct node{
int w,len,id,tot;
int kx[50];
}a[50];
inline int read(){
int x=0,w=0;char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) {x=(x<<3) (x<<1) (ch^48);ch=getchar();}
return w?-x:x;
}
void ycl(){
for(int i=2;i<=2000;i ){
if(!v[i]) v[i]=1,b[ num]=i,prime[i]=1;
for(int j=1;i*b[j]<=2000&&j<=num;j ){
v[b[j]*i]=1;
if(i%b[j]==0) break;
}
}
}
bool cmp(node x,node y){return x.tot <y.tot;}
int main(){
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
n=read();
for(int i=1;i<=n;i ) a[i].w=read(),a[i].id=i;
ycl();
for(int i=1;i<=n;i )
for(int j=i 1;j<=n;j )
if(prime[a[i].w a[j].w]){
s[i][j]=s[j][i]=1;
a[i].kx[ a[i].tot]=j;
a[j].kx[ a[j].tot]=i;
a[i].len ,a[j].len ;
}
sort(a 1,a n 1,cmp);
for(int i=1;i<=n;i ){
if(a[i].tot==0||use[i]) continue;
int we=INF,uo=0;
bool ti=1;
// cout<<a[i].w<<endl;
while(a[i].tot){
for(int j=1;j<=n;j ){
if(s[a[i].id][a[j].id]&&!use[j]){
// cout<<a[i].w<<" "<<a[j].w<<endl;
if(a[j].tot<we) we=a[j].tot,uo=j;
}
}
if(we==INF) break;
if(!ans[a[uo].w a[i].w]&&!use[uo]){
res ;//cout<<a[uo].w<<" res "<<a[i].w<<endl;
use[uo]=use[i]=1;
s[a[i].id][a[uo].id]=s[a[uo].id][a[i].id]=0;
ans[a[we].w a[i].w]=1;
break;
}
else a[i].tot--;
s[a[i].id][a[uo].id]=s[a[uo].id][a[i].id]=0;
}
}
printf("%d\n",res);
return 0;
}
1：4811. 排队
考场10分code
考场时不熟悉vector，想不出如何排序（真的是zz
维护一个堆
1操作 将堆顶出堆
2操作 倍增找到从修改的点到根这条链上第一个被标记的点，然后答案就是深度差
（60变10分TvT //考场爆10 //
#include<bits/stdc .h>
using namespace std;
const int maxn=1e5 10,N=5010;
int n,t,num,tot,ans1,ans2;
bool v[maxn],w=0;
int a[N][N],len[maxn],dep[maxn],fa[maxn],fdep[maxn];
inline int read(){
int x=0,w=0;char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) {x=(x<<3) (x<<1) (ch^48);ch=getchar();}
return w?-x:x;
}
void solve(int x,int k){//
if(k==0) return;
for(int i=1;i<=len[x];i ){
int y=a[x][i];
if(dep[y]==dep[x] 1&&!v[y]&&num){
solve(y,k-1);
if(num>0){
num--;v[y]=1;
if(num==0) ans1=y;
// printf("num:%d y:%d\n",num,y);
}
}
}
if(num==1&&x==1){
if(!v[x]) {
v[x]=1;num--;if(num==0) ans1=x;return;
}
}
}
void chan(int x){
ans2=0;
while(x!=0){
if(v[fa[x]]) {
ans2 ;v[fa[x]]=0;v[x]=1;
}
else break;
x=fa[x];
}
return;
}
void bl(int x,int k){
//建树
dep[x]=k 1;fdep[k 1]=x;
// printf("x:%d dep[x]:%d\n",x,dep[x]);
for(int i=1;i<=len[x];i ){
if(!dep[a[x][i]]){
fa[a[x][i]]=x;
bl(a[x][i],dep[x]);
}
}
}
int main(){
freopen("queue2.in","r",stdin);
freopen("ans.out","w",stdout);
int op=0,x,y;
n=read(),t=read();
for(int i=1;i<n;i ){
x=read(),y=read();
a[x][ len[x]]=y;a[y][ len[y]]=x;
// add(x,y);
}
for(int i=1;i<=n;i ){
sort(a[i] 1,a[i] len[i] 1);
if(len[i]>2) w=1;
}
bl(1,0);
if(!w){
for(int i=1;i<=t;i ){
op=read(),x=read();
if(op==1){
num =x;//num当前有多少人
ans1=fdep[n-num 1];
printf("%d\n",ans1);
}
else{
//1num
ans2=dep[x]-dep[n-num 1];
num--;
printf("%d\n",ans2);
}
}
return 0;
}
for(int i=1;i<=t;i ){
op=read(),x=read();
if(op==1){
num=x;
solve(1,x);
printf("%d\n",ans1);
}
else {
v[x]=0;chan(x);
printf("%d\n",ans2);
}
}
return 0;
}
满分 #include<bits/stdc .h>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1e5 10;
int n,t,fir[maxn],ffir[maxn],du[maxn],dep[maxn];
int num,tot,sum,fa[maxn][22];
bool v[maxn];
vector<int>q[maxn];
priority_queue<int>dui;
inline int read(){
int x=0,w=0;char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) {x=(x<<3) (x<<1) (ch^48);ch=getchar();}
return w?-x:x;
}
void dfs(int x,int k){
for(int i=0,y;i<q[x].size();i ){
y=q[x][i];
if(dep[y]) continue;
dep[y]=k 1;
dfs(y,k 1);
fir[y]=num;
ffir[num]=y;fa[y][0]=x;
dui.push(num);
num--;
}
}
inline int solve(int x){
if(!v[fir[fa[x][0]]]) {
// printf("x:%d fa:%d\n",x,fa[x][0]);
dui.push(fir[x]);
num--;
v[fir[x]]=0;
return 0;
}
int p=x;
for(int i=20;i>=0;i--)
if(fa[p][i]&&v[fir[fa[p][i]]]) p=fa[p][i];
dui.push(fir[p]);num--;
v[fir[p]]=0;
return dep[x]-dep[p];
}
int main(){
n=read(),t=read();
int x,y;
num=n;
for(int i=1;i<n;i ){
x=read(),y=read();
q[x].push_back(y);q[y].push_back(x);
}
for(int i=1;i<=n;i )
sort(q[i].begin(),q[i].end());
dep[1]=1;
dfs(1,1);
fir[1]=num;ffir[num]=1;dui.push(num);num--;
for(int i=1;i<=20;i )
for(int j=1;j<=n;j )
fa[j][i]=fa[fa[j][i-1]][i-1];
int op=0;
for(int i=1;i<=t;i ){
op=read(),x=read();
if(op==1){
sum =x;
int p=0;
while(num<sum) {
p=dui.top();
// printf("p:%d\n",p);
v[p]=1;
dui.pop(),num ;
// cout<<num<<endl;
}
printf("%d\n",ffir[p]);
}
else{
sum--;
int p=solve(x);
printf("%d\n",p);
}
}
return 0;
}
2：4867. 心理学概论
双二分
以ai为第一关键字，bi为第二关键字，ci为第三关键字进行排序 (x.ai<y.ai)||(x.ai==y.bi&&x.bi<y.bi)||(x.ai==y.ai&&x.bi==y.bi&&x.ci<y.ci)
先二分第一个兔子的位置，在二分第二个兔子的位置，
提前处理只分给一个兔子的情况
很容易证明如果将前i个篮子给第一个兔子，那前i-1个也应该分给第一个兔子
将剩下的篮子再按照同样的思路分给第二个兔子，剩下的就给第三个兔子 #include<bits/stdc .h>
using namespace std;
const int maxn=1e5 19;
int n,ma,mb,mc;
int ans,res;
struct node{
int ai,bi,ci;
}a[maxn],c[maxn];
inline int read(){
int x=0,w=0;char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) {x=(x<<3) (x<<1) (ch^48);ch=getchar();}
return w?-x:x;
}
bool cmp1(node x,node y)
{return (x.ai<y.ai)||(x.ai==y.bi&&x.bi<y.bi)||(x.ai==y.ai&&x.bi==y.bi&&x.ci<y.ci);}
int main(){
/* freopen("psy.in","r",stdin);
freopen("psy.out","w",stdout);*/
n=read();
int m1,m2,m3;
for(int i=1;i<=n;i ){
a[i].ai=read(),a[i].bi=read();a[i].ci=read();
ma=max(a[i].ai,ma);mb=max(mb,a[i].bi);mc=max(mc,a[i].ci);
}
ans=min(ma,min(mb,mc));
sort(a 1,a n 1,cmp1);
int l=0,r=n;
while(l<r){
res=0;
// printf("l:%d r:%d\n",l,r);
int mid=(l r)/2;
int lb=0,rb=n;
bool k=1;//初始化为1
while(lb<rb){
int mi=(lb rb)/2;
if(mi==mid){//不在同一组中
if(mi-1>=l) mi=mi--;
else if(mi 1<=r) mi=mi ;
else{
k=0;break;
}
}
int w=0;
for(int i=mid 1;i<=n;i ){
if(a[i].bi<=a[mi].bi) continue;//肯定分给了b，不再考虑
if(a[i].ci>w) w=a[i].ci;//
}
res=a[mid].ai a[mi].bi w;
if(res<ans){
ans=res;
k=1;
rb=mi;
}
else lb=mi 1;
}
if(k) r=mid;//已满足条件，就让a更小
else l=mid 1;
}
printf("%d",ans);
return 0;
}
借鉴大佬题解 来源：http://www./content-4-133701.html
|
