天梯赛校内选拔赛[A,B,C,D,E,F,G,H,J,L]
不会就是不会，没打好就是没打好，并不会为自己去狡辩
A.A+B Problem
简单的暴力，特判一下与最大值相等的情况就可以
#include<bits/stdc++.h>
const int N=1e5+10;
int a[N],b[N];
int main(){
int n;std::cin>>n;int maxl=-1000;
for(int i=1;i<=n;i++)std::cin>>a[i],b[i]=a[i],maxl=std::max(maxl,a[i]);
std::sort(b+1,b+1+n);
for(int i=1;i<=n;i++)if(a[i]!=b[n])std::cout<<a[i]+b[n]<<" ";else std::cout<<a[i]+b[n-1]<<" ";
}
B.Komorebi的数学课
是一个快速幂的板子，然而我不会手写
#include<bits/stdc++.h>
#define int long long
int n,m;
int qmi(int a,int b,int p){
int res=1%p;
while(b){
if(b&1)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
void solve(){
std::cin>>n;
std::cout<<qmi(n,n,n+2);
}
signed main(){
solve();
return 0;
}
C.次佛锅
有一个坑，就是一种食材的数量可以是两位数，我之前当成了一位数一直WA
#include<bits/stdc++.h>
std::map<std::string,int>mp;
signed main(){
std::string s;int n;
while(std::cin>>s){
if(s[0]<='9'&&s[0]>='0'){
for(auto it:s){
n=n*10+it-'0';
}
break;
}
std::cin>>n;
if(!mp[s])mp[s]=n;
else mp[s]+=n;
}
while(std::cin>>s){
std::cout<<mp[s]<<std::endl;
}
}
D. Setsuna的K数列
根据打表我们可以知道，由哪些数组成与下标的二进制有关，二进制的某一位是1，那么其对应的数就是存在的，否则就是不存在的
别忘了#define int long long
#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
int n,m,k;
int ans;
void solve(){
//try it again.
std::cin>>n>>k;int m=1;
while(n){
if(n&1)(ans+=m)%=mod;
n>>=1;(m*=k)%=mod;
}
std::cout<<ans<<std::endl;
}
signed main(){
solve();
return 0;
}
E.Wiki下象棋
这样的题在求最少的步数的时候最好初始化成-1，我之前初始化成0x3f，然后就只对了一个点
就是普通的BFS加点if
#include<bits/stdc++.h>
const int N=310;
bool bt[N][N];
int dist[N][N];
int n,m,k,a,b,c,d;
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
bool tyes(int i,int x,int y){
if(i==0)if(bt[x][y+1]==true)return false;
if(i==1)if(bt[x][y-1]==true)return false;
if(i==2)if(bt[x][y+1]==true)return false;
if(i==3)if(bt[x][y-1]==true)return false;
if(i==4)if(bt[x+1][y]==true)return false;
if(i==5)if(bt[x+1][y]==true)return false;
if(i==6)if(bt[x-1][y]==true)return false;
if(i==7)if(bt[x-1][y]==true)return false;
return true;
}
bool yes(int x,int y){
if(x<1)return false;
if(x>n)return false;
if(y>m)return false;
if(y<1)return false;
return true;
}
int bfs(){
std::queue<std::pair<int,int>>q;
q.push({a,b});
dist[a][b]=0;
while(!q.empty()){
auto t=q.front();q.pop();
int x=t.first;
int y=t.second;
for(int i=0;i<=7;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(yes(nx,ny)&&!bt[nx][ny]&&dist[nx][ny]==-1){
q.push({nx,ny});
dist[nx][ny]=dist[x][y]+1;
}
}
}
return dist[c][d];
}
int bfs2(){
int ans=0;
std::queue<std::pair<int,int>>q;
q.push({a,b});
dist[a][b]=0;
while(!q.empty()){
auto t=q.front();q.pop();
int x=t.first;
int y=t.second;
for(int i=0;i<=7;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(yes(nx,ny)&&tyes(i,x,y)&&!bt[nx][ny]&&dist[nx][ny]==-1){
q.push({nx,ny});
dist[nx][ny]=dist[x][y]+1;
}
}
}
return dist[c][d];
}
void solve(){
std::cin>>n>>m>>k>>a>>b>>c>>d;
memset(dist,-1,sizeof dist);
memset(bt,0,sizeof bt);
for(int i=1;i<=k;i++){
int x,y;
std::cin>>x>>y;
bt[x][y]=true;
}
std::cout<<bfs()<<" ";
memset(dist,-1,sizeof dist);
std::cout<<bfs2()<<" ";
std::cout<<std::endl;
}
signed main(){
int __;std::cin>>__;
while(__--)solve();
}
F.黄金律法
根据样例可以发现是大小相结合的冲突值最小
#include<bits/stdc++.h>
const int N=1e5+10;
#define int long long
int a[N],b[N];
void solve(){
int n;std::cin>>n;
for(int i=1;i<=n;i++)std::cin>>a[i];
std::sort(a+1,a+1+n);
for(int i=1;i<=n;i++)std::cin>>b[i];
sort(b+1,b+1+n,std::greater<int>());
int res=0;
for(int i=1;i<=n;i++)res+=a[i]*b[i];
std::cout<<res<<std::endl;
}
signed main(){
int __;std::cin>>__;
while(__--)solve();
}
G.天气预报
记得#define int long long
#include<bits/stdc++.h>
#define int long long
const int N=3e6+10;
int n,m;
int a,b,c;
std::string s;
int t[N],T[N];
void solve(){
//try it again.
std::cin>>n>>a>>b;
std::cin>>s;s="?"+s;
for(int o=1;o<=n;o++)T[o]=T[o-1]+s[o]-'0';//前缀1的数量
for(int o=1;o<=n;o++)t[o]=o-T[o];//前缀0的数量
int ans=0;
for(int i=1;i<=n;i++){
auto t1=std::lower_bound(t+i,t+1+n,a+t[i-1]);//由当前位置开始的前缀1充足的位置
auto t2=std::lower_bound(T+i,T+1+n,b+T[i-1]);//由当前位置开始的前缀0充足的位置
int len1=t1-t,len2=t2-T;
if(*t1-t[i-1]>=a&&*t2-T[i-1]>=b){
ans+=n-std::max(len1,len2)+1;//头指针固定,尾指针可以一直扫到末尾
}
}
if(!a&&!b)ans++;//不存在也是一种情况
std::cout<<ans<<std::endl;
}
signed main(){
solve();
return 0;
}
H.叠硬币
记得之前总结过一次背包,关于存储转移状态可以看这个
但我以为这个是个二分,然后拿了20分
#include<bits/stdc++.h>
const int N=2e5+10;
int n,m;
int f[N],a[N],last[N];
void solve(){
//try it again.
std::cin>>n>>m;
for(int o=1;o<=n;o++)std::cin>>a[o];
std::sort(a+1,a+1+n,std::greater<int>());
memset(f,0x3f,sizeof f);f[0]=0;
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i];j--){
if(f[j]>=f[j-a[i]]+1){
f[j]=f[j-a[i]]+1;
last[j]=a[i];
}
}
}
if(f[m]!=0x3f3f3f3f)std::cout<<f[m]<<std::endl;
else std::cout<<-1<<std::endl;
int t=m;
while(last[t]){
std::cout<<last[t]<<" ";t=t-last[t];
}
}
signed main(){
solve();
return 0;
}
J.史东薇尔城
显然答案就是 从1到MaverickFW的距离加上从1到终点的距离
那么就push进去1号点跑一遍堆优化djsk就好
没有板子我不会写djsk,呵呵
#include<bits/stdc++.h>
const int N=1e6+10;
#define int long long
int dist[N];
bool st[N];
#define PII std::pair<int,int>
std::vector<PII>G[N];
signed main(){
int n,m;std::cin>>n>>m;
memset(dist,0x3f,sizeof dist);
dist[1]=0;
std::priority_queue<PII,std::vector<PII>,std::greater<PII>>q;
q.push({0,1});
while(m--){
int a,b,c;std::cin>>a>>b>>c;
G[a].push_back({b,c});
G[b].push_back({a,c});
}
while(!q.empty()){
auto [a,b]=q.top();q.pop();
if(st[b])continue;st[b]=true;
for(auto [v,w]:G[b]){
if(dist[v]>dist[b]+w){
dist[v]=dist[b]+w;
q.push({dist[v],v});
}
}
}
std::cin>>m;
while(m--){
int a,b;std::cin>>a>>b;
std::cout<<dist[a]+dist[b]<<std::endl;
}
}
L.剪绳子
显然是个二分,别忘了特判0的位置
要不然会丢30分
#include<bits/stdc++.h>
const int N=1e5+10;
int a[N],b[N];
int main(){
int n;std::cin>>n;
char c;double x;
std::set<double>t;
t.insert(0);t.insert(10);
for(int i=1;i<=n;i++){
std::cin>>c>>x;
if(c=='C'){
t.insert(x);
}
else{
if(x==0){
printf("%.5f\n",*t.upper_bound(x));
continue;
}
auto a=t.lower_bound(x);
if(!(*a)){
printf("%.5f\n",10.00000-*(--a));
}
else printf("%.5f\n",*a-*(--a));
}
}
}
