題解-CF333

CF333

---

A Secrets

題意:用一種面額為 \(3^k\) 且不能整除 \(n\) 的硬幣,交付超過 \(n\) 元,要求超過最少且硬幣用得最多。

直接模擬即可,后面兩個要求是等價的。

#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef double db;#define x first#define y second#define bg begin()#define ed end()#define pb push_back#define mp make_pair#define sz(a) int((a).size())#define R(i,n) for(int i(0);i<(n);++i)#define L(i,n) for(int i((n)-1);~i;--i)const int iinf=0x3f3f3f3f;const ll linf=0x3f3f3f3f3f3f3f3f;//Data//Mainint main(){    ios::sync_with_stdio(0);    cin.tie(0),cout.tie(0);    ll n,now=1; cin>>n;    while(true){        now*=3;        if(n%now!=0){            cout<<(n/now)+1<<'\n';            break;        }    }    return 0;}

---

B Chips

每行每列最多選一個,任意行列行徑不可相交。

用以下方案:對于 \(\frac{n}{2}\) 前后反向。

	v
			<
>
		^

如果 \(n\in \rm{even}\),直接把空行空列都選上即可。

如果 \(n\in \rm{odd}\) 且中間行、列都空,答案 \(-1\)。

#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef double db;#define x first#define y second#define bg begin()#define ed end()#define pb push_back#define mp make_pair#define sz(a) int((a).size())#define R(i,n) for(int i(0);i<(n);++i)#define L(i,n) for(int i((n)-1);~i;--i)const int iinf=0x3f3f3f3f;const ll linf=0x3f3f3f3f3f3f3f3f;//Dataconst int N=1000;int n,m;bool ban[N<<1];//Mainint main(){    ios::sync_with_stdio(0);    cin.tie(0),cout.tie(0);    cin>>n>>m;    R(i,m){        int u,v; cin>>u>>v,--u,--v;        ban[u]=ban[v+n]=true;    }    int ns=0;    R(i,n-1)if(i){        if(!ban[i]) ns++;        if(!ban[i+n]) ns++;    }    if((n&1)&&!ban[n>>1]&&!ban[(n>>1)+n]) ns--;    cout<<ns<<'\n';    return 0;}

---

C Lucky Tickets

好像是什么煩人的毒瘤題,不做了。

---

D Characteristics of Rectangles

很明顯是要在二分以后判斷有沒有四柱。

設 \(vis_{p,q}\) 表示是否有一行 \(i\) 滿足 \(a_{i,p}=a_{i,q}=1\)。

可以枚舉每行,把 \(1\) 的下標丟進 vector,然后枚舉 \(p,q\in\) vector:

如果 \(vis_{p,q}\) 直接 return true,否則 \(vis_{p,q}=1\)。

因為算法復雜度和 \(vis\) 數組大小線性相關,所以時間復雜度 \(\Theta(n^2\log(a))\)。

還有個 \(\Theta(n^2\log(n))\) 的:sort 完同上操作一次。

#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef double db;#define x first#define y second#define bg begin()#define ed end()#define pb push_back#define mp make_pair#define sz(a) int((a).size())#define R(i,n) for(int i(0);i<(n);++i)#define L(i,n) for(int i((n)-1);~i;--i)const int iinf=0x3f3f3f3f;const ll linf=0x3f3f3f3f3f3f3f3f;//Dataconst int N=1000;int n,m,a[N][N];//Functionsbool vis[N][N];bool check(int mid){    R(j,m)R(i,j) vis[i][j]=false;    R(i,n){        vector<int> one;        R(j,m)if(a[i][j]>=mid) one.pb(j);        R(j,sz(one))R(i,j){            if(vis[one[i]][one[j]]) return true;            vis[one[i]][one[j]]=true;        }    }    return false;}//Mainint main(){    ios::sync_with_stdio(0);    cin.tie(0),cout.tie(0);    cin>>n>>m;    R(i,n)R(j,m) cin>>a[i][j];    int l=-1,r=1e9+1,mid;    while(r-l>1) mid=(l+r)>>1,(check(mid)?l:r)=mid;    cout<<l<<'\n';    return 0;}

---

E Summer Earnings

其實是水題,腦子不好使了。

要求最小邊最大的三角形。

把 \(\frac {n(n-1)}{2}\) 條邊從長到短排序,直到連出三角形。

用 bitset 優化,如果當前邊連的兩點的 bitset 或起來以后有 \(1\) 就可以了。

有 \(1\):bitset::any()。

#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef double db;#define x first#define y second#define bg begin()#define ed end()#define pb push_back#define mp make_pair#define sz(a) int((a).size())#define R(i,n) for(int i(0);i<(n);++i)#define L(i,n) for(int i((n)-1);~i;--i)const int iinf=0x3f3f3f3f;const ll linf=0x3f3f3f3f3f3f3f3f;//Dataconst int N=3000;int n;//Geometryusing P=pair<db,db>; P p[N];db dis(const P &a,const P &b){    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}//Graphusing edge=pair<db,pair<int,int>>;vector<edge> et;bitset<N> ec[N];//Mainint main(){    ios::sync_with_stdio(0);    cin.tie(0),cout.tie(0);    cout.precision(12);    cin>>n;    R(i,n) cin>>p[i].x>>p[i].y;    R(j,n)R(i,j) et.pb(mp(dis(p[i],p[j]),mp(i,j)));    sort(et.bg,et.ed,greater<edge>());    db ans=-iinf;    for(const edge &e:et){        if((ec[e.y.x]&ec[e.y.y]).any())            {ans=e.x*.5;break;}        ec[e.y.x].set(e.y.y),ec[e.y.y].set(e.y.x);    }    assert(ans>-100);    cout<<fixed<<ans<<'\n';    return 0;}

---

\[\Big\rm {George1123\ is\ very\ no.}\]