记录丢人点滴
虽然真的很丢人 但是看了一下大家代码发现我至少代码还是短(?
A: Contest for Robots
题目链接 题意：两种机器人对于n个问题有会和不会(1和0) 希望第一种的得分比第二种高 要如何安排问题分数分布 要求分数中最大的尽量小 算一下第一种比第二种多的1和0 除一下 可能会除零 要先判掉再除
代码语言：javascript复制#include<bits/stdc .h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; i)
using namespace std;
int a[105],b[105];
int main(){
int n,c1(0),c2(0); sc(n);
rep(i,0,n) sc(a[i]);
rep(i,0,n){
sc(b[i]);
if(a[i]==b[i]) continue;
else if(a[i]>b[i]) c1 ;
else c2 ;
}
if(!c1) return pf("-1n"),0;
int ans=(c2 c1)/c1;
pf("%dn",ans>0?ans:0);
}B: Journey Planning
题目链接 题意：希望选择b的总和尽量大且满足选中的bi,bj有i-j==bi-bj 每个b去减去i 找相同的 数组存的话加上n也行 但是map就是香啊 要ll 赛时比较草率qwq
代码语言：javascript复制#include<bits/stdc .h>
#define pf printf
#define sc(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=s; i<e; i)
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
const int maxn = 2e5 5;
int a[maxn];
map<int,int>ans;
signed main(){
int n,mx(0); sc(n); rep(i,1,n 1){
sc(a[i]); int t=a[i]-i; ans[t] =a[i];
}
for(auto& x:ans) mx=max(mx,x.second);
pf("%lldn",mx);
}C: Remove Adjacent
题目链接 题意：给一个字符串 对于每个字符 如果相邻字符有ascii码刚好比自己少1的 则可以删除 问最多能删多少个 枚举z到a 每次for一遍删 O(26*n^3)
代码语言：javascript复制#include<bits/stdc .h>
#define rep(i,s,e) for(ll i=s; i<e; i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
int main(){
ios::sync_with_stdio(0);
int n,cnt(0); string s; cin>>n>>s; s =' ';
dep(k,25,1) rep(i,0,n) if(s[i]==k 'a'){
if(s[i 1]==s[i]-1||(i&&s[i-1]==s[i]-1)) s.erase(i,1),n--,cnt ,i=i?i-2:-1;
} cout<<cnt;
}D: Navigation System
题目链接 题意：高德地图持续为您规划路线 n个点m条边的有向无权图 给k个点是必须经过的 导航每次路线会选择最短路 如果不是最短路就rebuild重新找最短路 问rebuild的最少和最多次数 无权图 bfs/dij/spfa啥的都行qwq 判是不是最短路用dis就行 mx和mn就差在有多条最短路的时候 这时候记一下就好了
代码语言：javascript复制#include<bits/stdc .h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(ll i=s; i<e; i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 5;
struct node{
int id,dt;
bool operator < (const node a) const{
return dt>a.dt;
}
};
priority_queue<node>q;
int n,m,k,s,t,tot;
int dis[maxn],vis[maxn],head[maxn],cnt[maxn];
int nex[maxn<<1],to[maxn<<1],val[maxn<<1];
void addedge(int u,int v,int w){
nex[ tot]=head[u];
head[u]=tot; to[tot]=v; val[tot]=w;
}
void dij(int s){
rep(i,1,n 1) dis[i]=1e9; dis[s]=0;
q.push({s,0}); while(!q.empty()){
int fr=q.top().id; q.pop();
if(vis[fr]) continue; vis[fr] ;
for(int j=head[fr];j;j=nex[j])
if(dis[to[j]]>val[j] dis[fr]&&!vis[to[j]]){
dis[to[j]]=val[j] dis[fr];
q.push({to[j],dis[to[j]]});
}
else if(dis[to[j]]==val[j] dis[fr])
cnt[to[j]]=1;
}
} // 板子闭着眼一套
int p[maxn];
int main(){
int mn(0),mx(0); sc(n); sc(m); while(m--){
int u,v; sc(u); sc(v); addedge(v,u,1);
} sc(k); rep(i,1,k 1) sc(p[i]);
dij(p[k]); rep(i,1,k 1){
if(i!=k&&dis[p[i]]!=dis[p[i 1]] 1) mn ;
else mx =cnt[p[i]];
} pf("%d %dn",mn,mn mx);
}E: World of Darkraft: Battle for Azathoth
题目链接 补了加qwq
