AtCoder Beginner Contest 164 题解

这次的前三题没有一点思考的必要啊（

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 '
'
#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 '
'
#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;
}