目录
A Quality-Adjusted Life-Year
签到
B Gwen’s Gift
C Forest for the Trees
gcd
const int maxn=5e5+7;
const int inf=0x3f3f3f3f;
ll n,m,t,p,q;
ll a[2],b[2];
inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }
int main(){
ll x1,x2,y1,y2;
n=read(); m=read();
x1=read(); y1=read();
x2=read(); y2=read();
t=gcd(n,m);
if(t==1){
printf("Yes");
return 0;
}
p=n/t; q=m/t;
if(x1<=p&&y1<=q){
if(x2>=n-p&&y2>=m-q){
printf("Yes");
return 0;
}
ll k=x2/p;
if(x2%p!=0) k++;
a[0]=k;
k=y2/q;
if(y2%q!=0) k++;
k=min(k,a[0]);
printf("No
");
printf("%lld %lld",p*k,q*k);
}
else{
printf("No
");
printf("%lld %lld",p,q);
}
}
D H-Index
签到 二分
vector<int> v;
bool check(int x) {
int cnt = 0;
for (int i = v.size() - 1;i >= 0;i--) {
if (v[i] >= x) cnt++;
else {
break;
}
}
return cnt >= x;
}
int main() {
int n; scanf("%d", &n);
for (int i = 1;i <= n;i++) {
int x; scanf("%d", &x);
v.push_back(x);
}
sort(v.begin(), v.end());
int l = 0, r = 1e9;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l;
return 0;
}
E Driving Lanes
dp
根据题意，我们知道在弯道的情况下，行走的路程是
s
+
c
∗
i
s + c * i
s+c∗i，其中
i
i
i表示的是处于第几道，当
c
c
c大于0的情况下，要使得
i
i
i尽可能地小，在
c
c
c小于0的情况下，要使得
i
i
i尽可能地大，按照贪心的情况，我们可以直接对应
1
1
1,
m
m
m，所以开始可以考虑贪心，但是要注意在变道的过程中，在直线上行驶的过程中也会多产生一部分代价，所以说在这个过程中，不一定是两个极端的车道1,m更优，而可能是在中间某一个车道产生了最优解，所以这里就不能够在使用贪心来解决，这里我们应该考虑用
d
p
dp
dp
ac_code:
int n,m,kk,r;
int a[2007];
int s[2007],c[2007];
int dp[307][307];
int main() {
n = read,m = read,kk = read,r = read;
r += kk;
for(int i=1; i<=n; i++) a[i] = read;
for(int i=1; i<n; i++) s[i]=read,c[i]=read;
int ans = 0;
Clear(dp,0);
dp[0][1] = 1;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(dp[i-1][j] == 0) continue;
int t = dp[i-1][j];
for(int k=1; k<=m; k++) {
if(a[i] >= abs(k - j) * kk) {
if(!dp[i][k]) dp[i][k] = t + abs(k - j) * r + a[i] - abs(k - j) * kk + s[i] + c[i] * k;
else dp[i][k] = min(dp[i][k],t + abs(k - j) * r + a[i] - abs(k - j) * kk + s[i] + c[i] * k);
// debug(dp[i][k]);
}
}
}
}
cout << dp[n][1] - 1 << endl;
return 0;
}
/**
4 3
5 2
10
10
10
10
4 -1
4 -1
4 1
->51
4 3
5 2
10
10
10
10
10 -3
10 -3
10 1
->61
**/
F Treasure Spotting
计算几何
重判没了
G Neighborhood Watch
问有多少条道路经过了给出的地点，其中起点和终点可以相同
typedef long long ll;
int a[200010], R[200010];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1;i <= m;i++) {
int x; scanf("%d", &x);
a[x] = 1;
}
int idx = n + 1;
for (int i = n;i >= 1;i--) {
if (a[i] == 0) R[i] = idx;
else idx = i;
}
ll res = 0;
for (int i = 1;i <= n;i++) {
if (a[i] == 1) res += n - i;
else {
if (R[i] != n + 1) {
res += n - R[i] + 1;
}
}
}
res += m;
printf("%lld", res);
return 0;
}
H Small Schedule
重判没了
I Mr. Plow King
贪心
ll cal(ll n,ll m) {
ll ret = 0;
while(m) {
ll x = (n - 1) * (n - 2) >> 1;
if(m > x) {
ret += x + 1;
m = x << 1,-- n;
} else ret += m,-- n,-- m;
}
return ret;
}
int main() {
ll n = read,m = read;
ll ret = 0;
cout << cal(n,m) << endl;
return 0;
}
/**
**/
J Rainbow Road Race
bfs
二进制
假如给每一个颜色一个标号为1<<x，其中x从1->6
这样一来，就可以转化为求最短路，终止的条件是经过的路径的颜色|（位运算或）之后，值为27-1，而在判断能不能走的时候也可以这样非常巧秒的判断能不能走
ac_code:
#define Clear(x,val) memset(x,val,sizeof x)
ll a[maxn << 1];
struct node {
int v,nex,w;
int col;
} e[maxn];
int cnt,head[maxn];
int get(char c) {
if(c == 'R') return 1;
if(c == 'O') return 2;
if(c == 'Y') return 3;
if(c == 'G') return 4;
if(c == 'B') return 5;
if(c == 'I') return 6;
if(c == 'V') return 7;
}
bool vis[3007][307];
ll dis[3007][307];
void init() {
cnt = 0;
Clear(head,-1);
}
void add(int u,int v,int w,int col) {
e[cnt].v = v;
e[cnt].w = w;
e[cnt].col = 1<<col;
e[cnt].nex = head[u];
head[u] = cnt ++;
}
struct Node {
int to;
ll w;
int col;
friend bool operator<(Node a,Node b) {
return a.w > b.w;
}
};
priority_queue<Node> que;
int tot[3007][3007];
int main() {
int n = read,m = read;
init();
char col;
for(int i=1; i<=m; i++) {
int u = read,v = read,w = read;
scanf("%c",&col);
int c = get(col) - 1;
add(u,v,w,c);
add(v,u,w,c);
}
que.push({1,0,0});// node 1 the tent
memset(dis,127 / 3,sizeof dis);
ll ans = 0;
int flag = 0;
while(que.size()) {
Node frt = que.top();
que.pop();
vis[frt.to][frt.col] = true;
if(frt.col == (1 << 7) - 1 && frt.to == 1) {
ans = frt.w;
flag = 1;
break;
}
int u = frt.to;
for(int i=head[u]; ~i; i=e[i].nex) {
int to = e[i].v;
int w = e[i].w;
int col = e[i].col;
int jue = col | frt.col;
if(vis[to][jue]) continue;// conted with node1
if(w + frt.w < dis[to][jue]) {
dis[to][jue] = w + frt.w;
que.push({to,w + frt.w,jue});
}
}
}
assert(flag);
cout << ans << endl;
return 0;
}
/**
7 7
1 2 1 R
2 3 1 O
3 4 1 Y
4 5 1 G
5 6 1 B
6 7 1 I
1 7 1 V
8 7
1 2 1 R
1 3 1 O
1 4 1 Y
1 5 1 G
1 6 1 B
1 7 1 I
1 8 1 V
**/