蒟蒻暂时只解了7道题,其他题目有想法但不一定对,没时间补了先搁着
(其实也并不想写但不写的话感觉浪费时间做题更不值..)
Problem A 第k大
被卡nlogn的STL了解一下?
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<bitset>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e6+11;
const int MOD = 2520;
const double eps = 1e-10;
typedef long long ll;
const int oo = 0x3f3f3f3f;
ll read(){
ll x=0,f=1;register 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;
}
ll res[maxn],n,a,b,c,k;
void C(int n,unsigned int A, unsigned int B, unsigned int c){
for(int i=0;i<n;i++){
res[i]=A+B;
A=((A<<2)+c)*i*29+B;
B=(((A+B)<<3)+c)*17;
}
}
int main(){
int T=read();
while(T--){
cin>>n>>a>>b>>c>>k;
C(n,a,b,c);
nth_element(res,res+n-k,res+n);
printf("%lld\n",res[n-k]);
}
}Problem B zhazhahe对于不重复数的研究
dfs
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
using namespace std;
const int maxn = 1e6+11;
typedef long long ll;
ll dp[maxn],tot;
bool vis[12];
int n;
//ll solve(ll t){
// ll tt=t+1,pos=0;
// while(tt){
// a[++pos]=tt%10;
// tt/=10;
// }
// rep(i,1,pos){
//
// }
// return tt;
//}
ll dfs(int cur,ll num,int st){
if(tot>1000005) return 0;
if(cur==0&&num==0) return dp[1]=0;
else if(cur==0) return dp[++tot]=num;
rep(i,0,9){
if(st&&i==0){
dfs(cur-1,0,1);
}
if((st&&i!=0)||(!st)){
if(!vis[i]){
vis[i]=1;
dfs(cur-1,num*10+i,0);
vis[i]=0;
}
}
}
}
int main(){
dfs(10,0,1);//cout<<tot<<endl;
// rep(i,1,100) cout<<i<<" "<<dp[i]<<endl;
int T; cin>>T;
while(T--){
scanf("%d",&n);
printf("%lld\n",dp[n]);
}
return 0;
}Problem D 颁奖
水题
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<bitset>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 6e4+11;
const int MOD = 2520;
const double eps = 1e-10;
typedef long long ll;
const int oo = 0x3f3f3f3f;
ll read(){
ll x=0,f=1;register 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;
}
bool vis[666];
int n,kind;
int a[666];
int main(){
while(cin>>n){
memset(vis,0,sizeof vis);
kind=0;
rep(i,1,n) a[i]=read();
rep(i,1,n){
if(a[i]&&!vis[a[i]]) kind++;
vis[a[i]]=1;
}
println(kind);
}
return 0;
}Problem E 跳一跳
水题,注意取模时防爆大小
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<bitset>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e6+11;
const int MOD = 2520;
const double eps = 1e-10;
typedef long long ll;
const int oo = 0x3f3f3f3f;
ll read(){
ll x=0,f=1;register 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;
}
ll res[maxn],n,a,b,c,k;
void C(int n,unsigned int A, unsigned int B, unsigned int c){
for(int i=0;i<n;i++){
res[i]=A+B;
A=((A<<2)+c)*i*29+B;
B=(((A+B)<<3)+c)*17;
}
}
int main(){
int T=read();
while(T--){
cin>>n>>a>>b>>c>>k;
C(n,a,b,c);
nth_element(res,res+n-k,res+n);
printf("%lld\n",res[n-k]);
}
}Problem H 三角形
CC特别喜欢三角形，他对三角形的性质了如指掌，他现在有n根木棍，长度为1、2、3……n，他现在从中选出X根木棍，
使得选出的木棍任意三根不能组成三角形，他现在想知道X最大是多少？
所求既两边之和小于等于第三边,边界条件f[i]=f[i-1]+f[i-2],斐波那契走起
PS.题目表述不明确,n<=2也算是合法的
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<bitset>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e5+11;
const int MOD = 2520;
const double eps = 1e-10;
typedef long long ll;
const int oo = 0x3f3f3f3f;
ll read(){
ll x=0,f=1;register 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;
}
ll fib[66666];
int main(){
fib[1]=1;fib[2]=2;
int up;
rep(i,3,oo){
if(fib[i-1]>1e18){
up=i-1;
break;
}else{
fib[i]=fib[i-1]+fib[i-2];
}
}
int T=read();
while(T--){
ll n=read();
// if(n<=2)println(0);
ll pos=lower_bound(fib+1,fib+1+up,n)-fib;
if(fib[pos]>n)pos--;
println(pos);
}
return 0;
}Porblem K 吃瓜群众rab0t
从小在北方长大的rab0t来到了广工，对这边的天气不太适应，特别是在夏天，这里的温度简直是热到爆炸，于是他爱上了吃冰镇西瓜。
但是瓜价格一般浮动比较大，经常出现今天瓜2块钱一斤，明天就要5块钱一斤，所以精打细算的rab0t要合理的吃瓜，使得他花的钱尽可能少
现在假设他从第一天开始要连续N天都有瓜可以吃，第i天的瓜卖Pi元，能吃Di天，如果某天买了新的瓜就会把没吃完的都扔掉，毕竟rab0t喜欢新鲜的食物。
问你他最少要花多少钱？
DP+线段树,详细参考我前一遍文章
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<bitset>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 6e4+11;
const int MOD = 2520;
const double eps = 1e-10;
typedef long long ll;
const int oo = 0x3f3f3f3f;
ll read(){
ll x=0,f=1;register 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;
}
ll dp[maxn],a[maxn],b[maxn],n;
struct ST{
ll mn[maxn<<2];
#define lc o<<1
#define rc o<<1|1
void build(int o,int l,int r){
mn[o]=oo;
if(l==r)return;
int m=l+r>>1;
build(lc,l,m);
build(rc,m+1,r);
}
void pu(int o){
mn[o]=min(mn[lc],mn[rc]);
}
void update(int o,int l,int r,int k,ll v){
if(l==r){
mn[o]=min(v,mn[o]);
return;
}
int m=l+r>>1;
if(k<=m) update(lc,l,m,k,v);
else update(rc,m+1,r,k,v);
pu(o);
}
ll query(int o,int l,int r,int L,int R){
if(L<=l&&r<=R) return mn[o];
int m=l+r>>1;
ll ans=oo;
if(L<=m) ans=min(ans,query(lc,l,m,L,R));
if(R>m) ans=min(ans,query(rc,m+1,r,L,R));
return ans;
}
}st;
int main(){
int T=read();
while(T--){
n=read();
rep(i,1,n) a[i]=read();
rep(i,1,n) b[i]=min(read(),n);
st.build(1,1,n);
dp[0]=0;
dp[1]=a[1];st.update(1,1,n,b[1],dp[1]);
rep(i,2,n){
dp[i]=dp[i-1]+a[i];
st.update(1,1,n,min(i+b[i]-1,n),dp[i]);//mai gua
ll t=st.query(1,1,n,i,n);//xu ming
if(t<dp[i]) dp[i]=t;
}
println(dp[n]);
}
return 0;
}Problem M 瓦西里的破车
瓦西里有一辆车，他要从家去邮局。
他家距邮局d公里。
瓦西里的车很差-它每行驶k公里就需要修理t秒后才能重新发动。
开车一公里汽车瓦西里需要花a秒，走一公里步行他需要花费b秒。(a<b)
你的任务是求瓦西里到达邮局的最短时间。
瓦西里可以在任何时候离开车开始步行。
写出函数,假设汽车走的历程为\(d_1\),那么\(f(d_1)=(a-b)*d_1+d*b+[(d_1-1)/k]*t\)
斜率不变那函数肯定单调
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e6+11;
const int oo = 0x3f3f3f3f;
const double eps = 1e-7;
typedef long long ll;
ll read(){
ll x=0,f=1;register 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;
}
ll k,a,b,t,d;
ll cal(ll d1){
if(d1==0) return d*b;
return (a-b)*d1+d*b+(d1-1)/k*t;
}
int main(){
while(cin>>d){
k=read();
a=read();
b=read();
t=read();
bool flag=0;
ll delta1=-(cal(d)-cal(1));
ll delta2=cal(k+1)-cal(k);
if(delta1>=delta2) flag=1;
if(flag) println(min(cal(d),cal(d-d%k)));//jiang
else println(cal(min(k,d)));
}
return 0;
}
转播
