A砝码
学了分组背包就会用2的前i个数可以组成1到（2i-1）的所有数，，然后109次方就是要小于232次方的然后暴力跑1到min(n,32)找最小值就行了
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x & (-x)
#define endl '\n'
#define ull unsigned long long
#define double long double
#define int long long
#define CI const int&
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
const int mod = 998244353;
const int inf = 1000000000000000000;
// const int inf=10000000000;
const int N=1e3+5;
// const int N=1000+10;
const ull hx = 13331;
const int M=3e6+10;
#define ll long long
void tt(){
int n,m;cin>>m>>n;
if(n<=32&&(1ll<<n)-1<m){
cout<<-1<<endl;
return;
}
int res=1,s=0,ans=inf;
for(int i=1;i<=min(n,32*1ll);i++){
s+=res;res*=2;
if(i==n){ans=min(ans,(1ll<<(i-1)));continue;}
if(i!=n&&s>=(m-s+n-i-1)/(n-i))ans=min(ans,max((1ll<<(i-1)),(m-s+n-i-1)/(n-i)));
}
cout<<ans<<endl;
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
long long t=1;
int res=1;
std::cin >> t;
while (t--)tt();
return 0;
}B变化的数组(Easy Version)
牛客练习赛137的C题去网上找题解
C贪心？
就是一个反悔贪心很模板的题，是一种思想，可以去做几个题就大概会了，有这个意识就行
完成文献阅读,完成学科三,完成思维导图无论是分开还是一起完成并没有影响，所有直接将他们加在一起，然后再按提交时间排序（从早到晚）然后用优先队列存选的每一门课程需要的时间，从1到n如果第i门课程能完成，那直接将他存进去就好，如果完成不了就贪心一下，第i个花的时间比选的课程中的最大的一个花的时间少就将花的时间多的那个替换的
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x & (-x)
#define endl '\n'
#define ull unsigned long long
#define double long double
#define int long long
#define CI const int&
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
const int mod = 998244353;
const int inf = 1000000000000000000;
const int N=5e5+10;
const ull hx = 13331;
const int M=3e6+10;
void tt(){
//反悔贪心
int n;cin>>n;
priority_queue<int>p;
vector<array<int,2>>a(n+1);
for(int i=1;i<=n;i++){
int x,y,z,t;cin>>x>>y>>z>>t;
a[i]={t,x+y+z};
}
sort(a.begin(),a.end());
int time=0;
for(int i=1;i<=n;i++){
if(a[i][0]-a[i-1][0]+time>=a[i][1]){
p.push(a[i][1]);
time=a[i][0]-a[i-1][0]+time-a[i][1];
}else{
time+=a[i][0]-a[i-1][0];
if(p.size()&&p.top()>a[i][1]){
time+=p.top();p.pop();
time-=a[i][1];p.push(a[i][1]);
}
}
}
cout<<p.size()<<endl;
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
long long t=1;
//std::cin >> t;
while (t--)tt();
return 0;
}D小苯的石子游戏
签到题，先按从大到小排序然后按题目意思模拟就好
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<math.h>
#include<string.h>
#include<deque>
#include<string>
#include<queue>
#include<cstring>
#include<string>
#include<numeric>
#include<bitset>
//#pragma GCC optimize(2)
using namespace std;
#define itn long long
#define int long long
#define endl '\n'
#define lowbit(x) x&(-x)
const int N = 200005;
bool cmp(int x, int y){
return x > y;
}
int a[N];
void tt()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n,cmp);
int sum1 = 0, sum2 = 0;
for (int i = 1; i <= n; i++)
{
if (i % 2)
sum1 += a[i];
else
sum2+=a[i];
}
if (sum1 > sum2)
cout << "Alice" << endl;
else
cout << "Bob" << endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
tt();
}
}E陨石降落（easy）
小学生都会，将x带进方程求出y就行
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x & (-x)
#define endl '\n'
#define ull unsigned long long
#define double long double
#define int long long
#define CI const int&
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
const int mod = 998244353;
const int inf = 1000000000000000000;
// const int inf=10000000000;
const int N=1e3+5;
// const int N=1000+10;
const ull hx = 13331;
const int M=3e6+10;
#define ll long long
void tt(){
int n;
cin>>n;
vector<double>a(n),b(n),c(n);
for(int i=0;i<n;i++){
double x,y;
cin>>x>>y;
a[i]=x,b[i]=y;
}
double aa,bb,cc;
cin>>aa>>bb>>cc;
for(int i=0;i<n;i++){
double xx=a[i],yy;
yy=(-aa*xx-cc)/bb;
cout<<fixed<<setprecision(6)<<xx<<" "<<yy<<endl;
}
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
long long t=1;
int res=1;
// std::cin >> t;
while (t--)tt();
return 0;
}F陨石降落（hard）
就是找垂点，可以去网上找一些计算几何的模板
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x & (-x)
#define endl '\n'
#define ull unsigned long long
#define double long double
#define int long long
#define CI const int&
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
const int mod = 998244353;
const int inf = 1000000000000000000;
// const int inf=10000000000;
const int N=1e3+5;
// const int N=1000+10;
const ull hx = 13331;
const int M=3e6+10;
#define ll long long
void tt(){
int n;
cin>>n;
vector<double>a(n),b(n),c(n);
for(int i=0;i<n;i++){
double x,y;
cin>>x>>y;
a[i]=x,b[i]=y;
}
double aa,bb,cc;
cin>>aa>>bb>>cc;
for(int i=0;i<n;i++){
double xx=a[i],yy,x1,y1;
yy=(-aa*xx-cc)/bb;
double k=-aa/bb;
if(yy>b[i]) y1=(yy-b[i])/(1+k*k)+b[i];
else y1=-(b[i]-yy)/(1+k*k)+b[i];
x1=(-bb*y1-cc)/aa;
cout<<fixed<<setprecision(6)<<x1<<" "<<y1<<endl;
}
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
long long t=1;
int res=1;
// std::cin >> t;
while (t--)tt();
return 0;
}直接贴模板的话就是
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);//圆周率,精确到15位小数3.141592653589793
const double eps = 1e-8;//偏差值，有时用1e-10，但是要注意精度
int sgn (double x) {
if (fabs(x) < eps) return 0;//x==0,返回0
else return x<0?-1:1;//x<0返回-1,x>0返回1
}
int dcmp(double x, double y){//比较两个浮点数
if (fabs(x-y)<eps)return 0;//x== y,返回0
else return x<y? - 1:1;//x<Y返回-1,x>y返回1
}
struct Point{
double x,y;
Point(){}
Point(double _x,double _y){
x=_x;
y=_y;
}
void input(){
scanf("%lf%lf",&x,&y);
}
void output(){
printf("%.2f␣%.2f\n",x,y);
}
//重载==
bool operator ==(Point b)const{
return sgn(x-b.x)==0&&sgn(y-b.y)==0;
}
//重载<
bool operator < (Point b)const{
return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;
}
//重载-
Point operator - (const Point&b)const{
return Point(x-b.x,y-b.y);
}
//叉积
double operator ^ (const Point&b)const{
return x*b.y-y*b.x;
}
//点积
double operator *(const Point&b)const{
return x*b.x+y*b.y;
}
//返回长度
double len(){
return hypot(x,y);//库函数
}
//返回长度的平方
double len2(){
return x*x+y*y;
}
//返回两点的距离
double distance(Point p){
return hypot(x-p.x,y-p.y);
}
//重载+
Point operator +(const Point&b)const{
return Point(x+b.x,y+b.y);
}
//重载*
Point operator *(const double &k)const{
return Point(x*k,y*k);
}
//重载/
Point operator /(const double &k)const{
return Point(x/k,y/k);
}
//计算pa和pb的夹角
//就是求这个点看a,b所成的夹角
//测试LightOJ1203
double rad(Point a,Point b){
Point p = *this;
return fabs(atan2(fabs((a-p)^(b-p)),(a-p)*(b-p)));
}
//化为长度为r的向量
Point trunc(double r){
double l=len();
if(!sgn(l))return*this;
r/=l;
return Point(x*r,y*r);
}
//逆时针旋转90度
Point rotleft(){
return Point(-y,x);
}
//顺时针旋转90度
Point rotright(){
return Point(y,-x);
}
//绕着p点逆时针旋转angle
Point rotate(Point p,double angle){
Point v = (*this)-p;
double c=cos(angle),s=sin(angle);
return Point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
}
};
struct Line{
Point s,e;
Line(){}
Line(Point _s,Point _e){
s=_s;
e=_e;
}
bool operator ==(Line v){
return (s==v.s)&&(e==v.e);
}
//根据一个点和倾斜角angle确定直线,0<=angle<pi
Line(Point p,double angle){
s=p;
if(sgn(angle-pi/2)==0){
e=(s+Point(0,1));
}
else{
e=(s+Point(1,tan(angle)));
}
}
//ax+by+c=0
Line(double a,double b,double c){
if(sgn(a)==0){
s=Point(0,-c/b);
e=Point(1,-c/b);
}else if(sgn(b)==0){
s=Point(-c/a,0);
e=Point(-c/a,1);
}else{
s=Point(0,-c/b);
e=Point(1,(-c-a)/b);
}
}
void adjust(){
if(e<s)swap(s,e);
}
//求线段长度
double length(){
return s.distance(e);
}
//返回直线倾斜角0<=angle<pi
double angle(){
double k=atan2(e.y-s.y,e.x-s.x);
if(sgn(k)<0)k+=pi;
if(sgn(k-pi)== 0)k-=pi;
return k;
}
//点和直线关系
//1在左侧
//2在右侧
//3在直线上
int relation(Point p){
int c=sgn((p-s)^(e-s));
if(c<0)return 1;
else if(c>0)return 2;
else return 3;
}
//点在线段上的判断
bool pointonseg(Point p){
return sgn((p-s)^(e-s))==0&&sgn((p-s)*(p-e))<=0;
}
//两向量平行(对应直线平行或重合)
bool parallel(Line v){
return sgn((e-s)^(v.e-v.s))==0;
}
//两线段相交判断
//2规范相交
//1非规范相交
//0不相交
int segcrossseg(Line v){
int d1=sgn((e-s)^(v.s-s));
int d2=sgn((e-s)^(v.e-s));
int d3=sgn((v.e-v.s)^(s-v.s));
int d4=sgn((v.e-v.s)^(e-v.s));
if((d1^d2)==-2&&(d3^d4)==-2)return 2;
return (d1==0&&sgn((v.s-s)*(v.s-e))<=0)||(d2==0&&sgn((v.e-s)*(v.e-e))<=0)||(d3==0&&sgn((s-v.s)*(s-v.e))<=0)||(d4==0&&sgn((e-v.s)*(e-v.e))<=0);
}
//直线和线段相交判断
//-*thisline-vseg
//2规范相交
//1非规范相交
//0不相交
int linecrossseg(Line v){
int d1=sgn((e-s)^(v.s-s));
int d2=sgn((e-s)^(v.e-s));
if((d1^d2)==-2)return 2;
return (d1==0||d2==0);
}
//两直线关系
//0平行
//1重合
//2相交
int linecrossline(Line v){
if((*this).parallel(v))
return v.relation(s)==3;
return 2;
}
//求两直线的交点
//要保证两直线不平行或重合
Point crosspoint(Line v){
double a1=(v.e-v.s)^(s-v.s);
double a2=(v.e-v.s)^(e-v.s);
return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
}
//点到直线的距离
double dispointtoline(Point p){
return fabs((p-s)^(e-s))/length();
}
//点到线段的距离
double dispointtoseg(Point p){
if(sgn((p-s)*(e-s))<0||sgn((p-e)*(s-e))<0)
return min(p.distance(s),p.distance(e));
return dispointtoline(p);
}
//返回线段到线段的距离
//前提是两线段不相交，相交距离就是0了
double dissegtoseg(Line v){
return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));
}
//返回点p在直线上的投影
Point lineprog(Point p){
return s+(((e-s)*((e-s)*(p-s)))/((e-s).len2()));
}
//返回点p关于直线的对称点
Point symmetrypoint(Point p){
Point q = lineprog(p);
return Point(2*q.x-p.x,2*q.y-p.y);
}
};
typedef Point Vector;
double Distance(Point A,Point B){return hypot(A.x-B.x,A.y-B.y);}
void tt(){
int n;cin>>n;
vector<Point>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
int x,y,z;cin>>x>>y>>z;
Line line(x,y,z);
for(int i=1;i<=n;i++){
Point pos=line.lineprog(a[i]);
printf("%.6f %.6f\n",pos.x,pos.y);
}
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
long long t=1;
//std::cin >> t;
while (t--)tt();
return 0;
}G小陆学长跳石头(eazy)（原题？）
签到,找两点相距最远的点就好,记得起点和终点
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x & (-x)
#define endl '\n'
#define ull unsigned long long
#define double long double
#define int long long
#define CI const int&
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
const int mod = 998244353;
const int inf = 1000000000000000000;
// const int inf=10000000000;
const int N=1e3+5;
// const int N=1000+10;
const ull hx = 13331;
const int M=3e6+10;
#define ll long long
void tt(){
int n,m;cin>>n>>m;
vector<int>a(n+1);
int ans=0;
for(int i=1;i<=n;i++){
cin>>a[i];
ans=max(ans,a[i]-a[i-1]);
}
ans=max(ans,m-a[n]);
cout<<ans<<endl;;
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
long long t=1;
int res=1;
// std::cin >> t;
while (t--)tt();
return 0;
}
Comments NOTHING