T1 购买饮料
题解
简单且傻逼的题目有人更傻逼没做出来
很容易就会想去拿最后能喝多少瓶去做未知量来求
然后就有一个严重的问题，它会赊账
非常明显这样算是不得行的
那么考虑换个思路
以能喝多少套饮料为未知量，先除去第一套，免得一套都买不起时赊账买了饮料
然后将剩余的钱除以 \(a\times x - b\) 顺带判一下无解，式子很简单就不解释了
那么我们得出来了这个值就很容易求出到底喝了多少瓶了
别忘了最后要统计一下最后凑不够一套时的瓶数
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,a,b;
signed main(){
freopen("buy.in","r",stdin);
freopen("buy.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--){
cin>>n>>x>>a>>b;
if(n<a*x){
cout<<n/x<<"\n";
continue;
}
if(a*x<=b){
cout<<"-1\n";
continue;
}
int t = (n-a*x)/(a*x-b)+1;
cout<<t*a+(n-t*(a*x-b))/x<<"\n";
}
return 0;
}
第二种是用二分找答案的方法，仅供参考
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,a,b;
signed main(){
freopen("buy.in","r",stdin);
freopen("buy.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--){
cin>>n>>x>>a>>b;
if(a*x<=b&&n>=a*x){
cout<<"-1\n";
continue;
}
if((n/x)<a){
cout<<n/x<<"\n";
continue;
}
int l = 0,r = 1e9;
while(l<r){
int mid = l+r>>1;
if(n-mid*(a*x-b)>=a*x) l = mid+1;
else r = mid;
}
cout<<(n-r*(a*x-b))/x+r*a<<"\n";
}
return 0;
}
T2 多边形
题解
一道构造题，偏向训练思维
如果存在一个颜色只出现了一次，那么直接把这个点和所有其他点相连即可
否则一定会出现相邻的三个点颜色两两不同，直接将这三个点划分成一个三角形，并删除掉中间那个点递归即可
容易发现所有限制条件始终满足。需要用链表来维护当前所有没有被删除的点
代码上没有什么难度
#include<bits/stdc++.h>
#define N ((int)1e6+10)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n,col[N<<1],u[N],v[N],stk[N],top;
char c[N];
vector<pii>ans;
int ne(int x){
return x==n?1:x+1;
}
int be(int x){
return x==1?n:x-1;
}
bool check(int x,int y,int z){
return col[x]!=col[y]&&col[x]!=col[z]&&col[y]!=col[z];
}
int main(){
freopen("polygon.in","r",stdin);
freopen("polygon.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>c+1;
for(int i = 1;i<=n;i++){
if(c[i]=='R') col[i] = 1;
if(c[i]=='B') col[i] = 2;
if(c[i]=='G') col[i] = 3;
}
int q = -1;
for(int i = 1;i<=n;i++){
if(check(be(i),i,ne(i))){
q = ne(i);
break;
}
}
stk[++top] = q;
for(int i = ne(q);i!=q;i = ne(i)){
while(top>=2&&check(stk[top-1],stk[top],i)){
ans.push_back({stk[top-1],i});
top--;
}
stk[++top] = i;
}
for(int i = 0;i<=n-4;i++)
cout<<ans[i].fi<<" "<<ans[i].se<<"\n";
return 0;
}
T3 二分图最大权匹配
题解
没改，不过需要先知道曼哈顿距离转切比雪夫距离
之前有一场考试中有相应模板，可以自行翻一下如果没看见就是我把那篇博客咕了
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const ll inf=1ll<<60;
int n;
ll ax[100005],ay[100005],bx[100005],by[100005],vin[100005][5],vout[100005][5],din[5],dout[5],dis[5][5];
set<pll> in[5],out[5],e[5][5];
void delin(int x,int y){
for(int i=1;i<=4;i++) in[i].erase(mp(vin[x][i],x));
for(int i=1;i<=4;i++) din[i]=in[i].empty()?inf:in[i].begin()->fi;
for(int i=1;i<=4;i++) if(i!=y) e[y][i].insert(mp(vin[x][i]-vin[x][y],x));
}
void delout(int x,int y){
for(int i=1;i<=4;i++) out[i].erase(mp(vout[x][i],x));
for(int i=1;i<=4;i++) dout[i]=out[i].empty()?inf:out[i].begin()->fi;
for(int i=1;i<=4;i++) if(i!=y) e[i][y].insert(mp(vout[x][i]-vout[x][y],-x));
}
void deledge(int x,int y){
int z=e[x][y].begin()->se;
if(z>0){
for(int i=1;i<=4;i++) if(i!=x) e[x][i].erase(mp(vin[z][i]-vin[z][x],z));
for(int i=1;i<=4;i++) if(i!=y) e[y][i].insert(mp(vin[z][i]-vin[z][y],z));
}
else{
z=-z;
for(int i=1;i<=4;i++) if(i!=y) e[i][y].erase(mp(vout[z][i]-vout[z][y],-z));
for(int i=1;i<=4;i++) if(i!=x) e[i][x].insert(mp(vout[z][i]-vout[z][x],-z));
}
}
ll f(int x,int y){return e[x][y].empty()?inf:e[x][y].begin()->fi;}
void delpath(int x,int y){
if(x==y) return;
int z=0,w=0;
for(int i=1;i<=4;i++){
if(i==x||i==y) continue;
if(!z) z=i;
else w=i;
}
ll mina=f(x,y); int opt=1;
if(chkmin(mina,f(x,z)+f(z,y))) opt=2;
if(chkmin(mina,f(x,w)+f(w,y))) opt=3;
if(chkmin(mina,f(x,z)+f(z,w)+f(w,y))) opt=4;
if(chkmin(mina,f(x,w)+f(w,z)+f(z,y))) opt=5;
if(opt==1) deledge(x,y);
if(opt==2) deledge(x,z),deledge(z,y);
if(opt==3) deledge(x,w),deledge(w,y);
if(opt==4) deledge(x,z),deledge(z,w),deledge(w,y);
if(opt==5) deledge(x,w),deledge(w,z),deledge(z,y);
}
void calc(){
for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) dis[i][j]=i==j?0:f(i,j);
for(int k=1;k<=4;k++) for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) chkmin(dis[i][j],dis[i][k]+dis[k][j]);
}
int main(){
freopen("match.in","r",stdin);freopen("match.out","w",stdout);
n=readint();
for(int i=1;i<=n;i++) ax[i]=readint(),ay[i]=readint();
for(int i=1;i<=n;i++) bx[i]=readint(),by[i]=readint();
for(int i=1;i<=n;i++){
int x=ax[i],y=ay[i];
ax[i]=x+y,ay[i]=x-y;
x=bx[i],y=by[i];
bx[i]=x+y,by[i]=x-y;
}
for(int i=1;i<=n;i++){
vin[i][1]=ax[i];
vin[i][2]=-ax[i];
vin[i][3]=ay[i];
vin[i][4]=-ay[i];
vout[i][1]=-bx[i];
vout[i][2]=bx[i];
vout[i][3]=-by[i];
vout[i][4]=by[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=4;j++){
in[j].insert(mp(vin[i][j],i));
out[j].insert(mp(vout[i][j],i));
}
}
for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) dis[i][j]=i==j?0:inf;
for(int i=1;i<=4;i++){
din[i]=in[i].begin()->fi;
dout[i]=out[i].begin()->fi;
}
ll ans=0;
for(int i=1;i<=n;i++){
ll mn=inf; pii opt=mp(0,0);
for(int j=1;j<=4;j++)
for(int k=1;k<=4;k++)
if(chkmin(mn,din[j]+dis[j][k]+dout[k])) opt=mp(j,k);
ans-=mn;
int x=in[opt.fi].begin()->se,y=out[opt.se].begin()->se;
delin(x,opt.fi);
delout(y,opt.se);
delpath(opt.fi,opt.se);
calc();
}
printf("%lld\n",ans);
return 0;
}
还想看我改T4？没门！
不过T4随机38分，属实难见
标签：校内,int,cin,long,231019,return,col,define From： https://www.cnblogs.com/cztq/p/17775461.html