传送门:https://atcoder.jp/contests/abc164
这次的前三题没有一点思考的必要啊(
F题看起来就不可做,日后看看吧
A
#include<bits/stdc++.h>
using namespace std;
int main(){
int s, w; cin>>s>>w;
if(w>=s) puts("unsafe"); else puts("safe");
return 0;
}
B
#include<bits/stdc++.h>
using namespace std;
int main(){
int a, b, c, d; cin>>a>>b>>c>>d;
while(a>0 || c>0){
c-=b;
if(c<=0){
puts("Yes");
return 0;
}
a-=d;
if(a<=0){
puts("No");
return 0;
}
}
return 0;
}
C
#include<bits/stdc++.h>
using namespace std;
int main(){
set<string> s;
int n; cin>>n;
while(n--){
string t; cin>>t;
s.insert(t);
}
cout<<s.size();
return 0;
}
D
经典套路题了。
和 https://atcoder.jp/contests/abc158/tasks/abc158_e 几乎一样hh
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
#define int long long
int buc[2021];
const int mod=2019;
int fpow(int x, int p){
int res=1;
for(; p; p>>=1, x=x*x%mod)
if(p&1) res=res*x%mod;
return res;
}
signed main(){
string s; cin>>s; int n=s.size();
int cur=0, bit=0;
dwn(i,n-1,0) cur=(fpow(10, bit)*(s[i]-'0')%mod+cur)%mod, buc[cur]++, bit++;
int res=buc[0]*(buc[0]+1)/2;
rep(i,1,2018) res+=buc[i]*(buc[i]-1)/2;
cout<<res<<endl;
return 0;
}
E
分析
二维 dijktra + 状态转移思想。
在一个城市 \(u\) ,有两个去处:
- 在原地买币(币增加,时间耗费增加)。
- 去其它城市(币减少,时间耗费增加)。
在建图的时候可以把第一个操作看做是:从 \(u\) 到 \(u\) ,然后时间耗费(边权)为题目所说的 \(D\) ,而币消耗为题目所说的 \(C\) 取负。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
#define int long long
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=55, M=N*N<<1;
int n, m, s;
int lim;
int S=1;
struct node{
int to, c, w, next;
}e[M];
int tot, h[N];
int C[N], D[N]; // coin and time
void add(int u, int v, int c, int w){
e[tot].to=v, e[tot].c=c, e[tot].w=w, e[tot].next=h[u], h[u]=tot++;
}
struct element{
int u, c, w;
bool operator < (const element &o)const{
return w==o.w? c>o.c: w>o.w;
}
};
int d[N][M];
bool vis[N][M];
void dijk(){
memset(d, 0x3f, sizeof d);
priority_queue<element> q;
d[S][s]=0;
q.push({S, s, 0});
while(q.size()){
auto hd=q.top(); q.pop();
int u=hd.u, c=hd.c, w=hd.w;
if(vis[u][c]) continue;
vis[u][c]=true;
for(int i=h[u]; ~i; i=e[i].next){
int go=e[i].to;
if(go==u && c>=lim) continue;
int t=c-e[i].c; t=min(lim, t);
if(t<0) continue;
if(d[go][t]>d[u][c]+e[i].w){
d[go][t]=d[u][c]+e[i].w;
q.push({go, t, d[go][t]});
}
}
}
}
signed main(){
memset(h, -1, sizeof h);
cin>>n>>m>>s;
rep(i,1,m){
int u, v, c, w; // cost dist
read(u), read(v), read(c), read(w); lim+=c;
add(u, v, c, w), add(v, u, c, w);
}
s=min(s, lim);
rep(i,1,n) read(C[i]), read(D[i]);
rep(i,1,n) add(i, i, -C[i], D[i]);
dijk();
rep(i,2,n){
int res=ll_INF;
rep(j,0,lim) res=min(res, d[i][j]);
cout<<res<<endl;
}
return 0;
}
F