|
正解：二分圖匹配
考場上想都沒想打了貪心
本以為會爆0，神奇的A了，驚了
（二分圖只練了模板，這么明顯的題目竟然沒想到 //3y7h貪心寫炸了
//驚了亂搞居然A了可能數(shù)據(jù)太水了吧
//正解二分圖
#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為第一關(guān)鍵字，bi為第二關(guān)鍵字，ci為第三關(guān)鍵字進行排序 (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
|
