Codeforces Round #367 (Div. 2)---水题 | dp | 01字典树

A.Beru-taxi

水题:有一个人站在(sx,sy)的位置,有n辆出租车,正向这个人匀速赶来,每个出租车的位置是(xi, yi) 速度是 Vi;求人最少需要等的时间;

单间循环即可;

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define N 102550
#define PI 4*atan(1.0)
#define mod 100000001
#define met(a, b) memset(a, b, sizeof(a))
typedef long long LL; int main()
{
int sx, sy, n;
double ans = INF;
scanf("%d %d %d", &sx, &sy, &n);
for(int i=; i<=n; i++)
{
int x, y, v;
scanf("%d %d %d", &x, &y, &v);
double d = sqrt((x-sx)*(x-sx)+(y-sy)*(y-sy));
ans = min(ans, d/v);
}
printf("%.7f\n", ans);
return ;
}

B.Interesting drink

 有n个物品,每个物品为ai元,某人每天有x元钱,求每天他能买几种的物品;

排序二分即可;

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define N 102550
#define PI 4*atan(1.0)
#define mod 100000001
#define met(a, b) memset(a, b, sizeof(a))
typedef long long LL; int a[N]; int main()
{
int n, m, num;
while(scanf("%d", &n)!=EOF)
{
for(int i=; i<n; i++)
scanf("%d", &a[i]);
sort(a, a+n);
scanf("%d", &m);
for(int i=; i<m; i++)
{
scanf("%d", &num);
int ans = upper_bound(a, a+n, num)-a;
printf("%d\n", ans);
}
}
return ;
}

C.Hard problem

 简单dp:给你n个字符串,然后问这n个字符串要想变成字典序排列的字符串所需的代价是多少,每个字符串可以倒置,(倒置串 i 的代价是a[i]),或者不变;

可以用dp[i][0]表示前i个字符串已经是按字典序排列的,并且第i个字符串不倒置的最小代价;用dp[i][0]表示前i个字符串已经是按字典序排列的,并且第i个字符串倒置的最小代价;

所以公式很容易写出来;

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define oo 1000000000000000
#define N 102550
#define PI 4*atan(1.0)
#define mod 100000001
#define met(a, b) memset(a, b, sizeof(a))
typedef long long LL; int n;
LL a[N], dp[N][]; char s[][N]; void Strrev(char str[])
{
int len = strlen(str);
for(int i=, j=len-; i<j; i++, j--)
swap(str[i], str[j]);
} int main()
{
scanf("%d", &n);
for(int i=; i<=n; i++)
{
scanf("%I64d", &a[i]);
dp[i][] = dp[i][] = oo;
} int p = ; dp[][] = ; dp[][] = a[]; for(int i=; i<=n; i++)
{
p = p^;
scanf("%s", s[p]);
if(i == ) continue; strcpy(s[p+], s[p]);
Strrev(s[p+]);
strcpy(s[(p^)+], s[p^]);
Strrev(s[(p^)+]); if(strcmp(s[p], s[p^]) >= )
dp[i][] = min(dp[i][], dp[i-][]);
if(strcmp(s[p], s[(p^)+]) >= )
dp[i][] = min(dp[i][], dp[i-][]);
if(strcmp(s[p+], s[p^]) >= )
dp[i][] = min(dp[i][], dp[i-][] + a[i]);
if( strcmp(s[p+], s[(p^)+]) >= )
dp[i][] = min(dp[i][], dp[i-][] + a[i]);
}
LL ans = min(dp[n][], dp[n][]);
if(ans == oo)ans = -;
printf("%I64d\n", ans);
return ;
}

D.Vasiliy's Multiset

01字典树:有一个里面初始值只有 0 的集合,执行 n 个操作,每个操作有三种可能:

+ x把x添加到集合中去;

- X把x从集合中删去一个;保证集和中一定有x;

? x从集合中找到一个数y,使得x异或y最大化;

对于每个?操作输出对应的最大的值;

01字典树模板:把十进制数转化为二进制数,通过前补零的方法构成32位,然后从前到后依次添加到字典树中去;

在查找时,每次尽量查找当前位相反的数的那个位置, 因为异或是不同为1的;

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define oo 1000000000000000
#define N 102550
#define PI 4*atan(1.0)
#define mod 100000001
#define met(a, b) memset(a, b, sizeof(a))
typedef long long LL; struct node
{
int sum, num;///sum表示有多少个数经过当前这个节点;num为从根节点到叶子节点表示的数;
node *Next[];///指向下一层的节点;
}; void Add(node *head, int x, int cnt)///把x对应的二进制01插入到字典树中去;共32位,前补零形式;
{
node *p = head;
for(int i=; i>=; i--)///这一点不太理解位运算的,但是相当于是把x转换成二进制,然后插入其中;
{
int k = (x>>i)&;
if(p->Next[k] == NULL)///当不存在当前节点时,开创新节点,并连接在对应位置;
{
node *q = new node();
p->Next[k] = q;
}
p = p->Next[k];///接着往下走;
p->sum += cnt;///更新节点经过数;
}
p->num = x;///结束的时候更新叶子节点对应的数;
} int Find(node *head, int x)
{
node *p = head;
for(int i=; i>=; i--)
{
int k = (x>>i)&;
if(p->Next[k^] != NULL && p->Next[k^]->sum > )///尽量找与k不同的;应为异或是不同为1,所以要想最大,就要尽量不同;
p = p->Next[k^];
else if(p->Next[k] != NULL && p->Next[k]->sum > )
p = p->Next[k];
}
return (p->num)^x;///返回对应的最大结果;
} int main()
{
int n, x; char ch; scanf("%d", &n); node *head = new node(); Add(head, , ); for(int i=; i<=n; i++)
{
scanf(" %c %d", &ch, &x);
if(ch == '+')
Add(head, x, );
else if(ch == '-')///删除,相当于更新sum即可;
Add(head, x, -);
else
{
int ans = Find(head, x);
printf("%d\n", ans);
}
}
return ;
}
上一篇:我对 Java 标识符的分类命名方法


下一篇:Codeforces Beta Round #37 A. Towers 水题