A.Blackjack
题意：
现在有(n)张卡片，每张都有一个数值(x_i)。
给定(a,b)，现在有一个人每次随机抽出一张卡片出来，并且加上其数值，如果数值和在((a,b])的范围内他就胜利；如果超过了(b)，他就输了。
他会一直抽下去，直到胜利或者失败。
现在问他获胜的概率为多少？
思路：
不是很懂的概率(dp)，我就说一下自己的理解吧，可能理解存在一些偏差。
-
因为胜利的条件是和落在区间((a,b])内，直接定义(dp)状态不好控制这最后一次。
-
所以考虑枚举抽取最后一张牌的数值，然后一张一张来(dp)，只要最后落在((a-x_i,b-x_i])内就行。
定义(dp[i][j][k])为：前(i)张牌中，抽取(j)张，总和为(k)的概率。那么就有转移方程：
[dp[i][j][k]+=dp[i-1][j-1][k-x_i]*j/(n-j+1)
]
一开始乘以(j)这里我有点疑惑，但想了一想，我们现在抽取卡牌是按照一定顺序来的，但实际同样抽取这些卡牌，顺序可能不一样。但有一点就是：不管顺序怎么样，概率是一样的。这个应该比较好验证。所以这里乘以(j)就相当于在最终乘了一个阶乘。
- 发现枚举最后一张需要(O(n))，(dp)转移需要(O(n^3))，显然时间复杂度要超，考虑优化。
- 因为有很多重复计算，所以考虑先求出不删除的状态，然后枚举最后一张，更新(dp)状态，使得状态中不包含这一张。
- 可逆背包！分析复杂度，枚举最后一张需要(O(n))的时间，每次删除和统计答案需要(O(n^2))的时间，时间复杂度说得过去。
在最终的状态中，要撤去一个的贡献，emmm，结合代码比较好解释：
for(int j = 1; j <= n; j++) {
for(int k = x[i]; k <= b; k++) {
dp[cur][j][k] -= dp[cur][j - 1][k - x[i]] * j / (n - j + 1);
}
}
这里的(dp[cur][j-1][k-x_i])是不含当前这个物品的背包，但我们(dp[cur][j][k])中会含有这个，那么我们就减去第(i)个物品的贡献。因为是从前往后，所以最后就能成功删去第(i)个物品的贡献了。
最后从后面往前加回贡献，从前往后的话就会重复加，类似于完全背包那样。
还需要慢慢消化一下呀~
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
int n, a, b;
double dp[2][N][N];
int x[N];
int main() {
cin >> n >> a >> b;
for(int i = 1; i <= n; i++) scanf("%d", &x[i]);
int cur = 0;
dp[0][0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= i; j++) {
for(int k = 0; k <= b; k++) {
dp[cur ^ 1][j][k] = dp[cur][j][k];
if(j && k >= x[i]) dp[cur ^ 1][j][k] += dp[cur][j - 1][k - x[i]] * j / (n - j + 1);
}
}
cur ^= 1;
}
double ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for(int k = x[i]; k <= b; k++) {
dp[cur][j][k] -= dp[cur][j - 1][k - x[i]] * j / (n - j + 1);
}
}
for(int j = 0; j < n; j++) {
for(int k = max(0, a + 1 - x[i]); k <= min(a, b - x[i]); k++) {
ans += dp[cur][j][k] / (n - j);
}
}
for(int j = n; j >= 1; j--) {
for(int k = x[i]; k <= b; k++) {
dp[cur][j][k] += dp[cur][j - 1][k - x[i]] * j / (n - j + 1);
}
}
}
printf("%.10f", ans);
return 0;
}
B.Coffee Chicken
题意：
定义(s(1)=)"COFFEE",(s(2)=)"CHICKEN"，(s(n)=s(n-2)+s(n-1))。
现在要求(s(n))的第(k)个，(1leq nleq 500,1leq kleq 10^{12})。
思路：
因为(k)比较小，递归求解即可。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
const ll MAX = 1e12;
int T;
ll f[N];
ll n, k;
char query(int n, ll k) {
if(n == 1) {
return "COFFEE"[k - 1];
} else if(n == 2) {
return "CHICKEN"[k - 1];
} else {
if(k <= f[n - 2]) return query(n - 2, k);
else return query(n - 1, k - f[n - 2]);
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
f[1] = 6, f[2] = 7;
for(int i = 3; i < N; i++) {
f[i] = min(MAX + 20, f[i - 1] + f[i - 2]);
}
cin >> T;
while(T--) {
cin >> n >> k;
for(ll i = k; i < min(k + 10, f[n] + 1); i++) cout << query(n, i);
cout << '
';
}
return 0;
}
C.Gifted Composer
题意：
有(n)个操作，每次操作在前面或者后面插入一个字符。
每次操作过后，需要输出循环节的数量。
例如：("abbab")，3,5都为其循环节长度，所以输出2。
思路：
十分巧妙的一道题。
- 对于长度为(x)的循环节，它一定会出现在时间(t=x)处，假设其结束在(t=y)。那么可知当(t>y)时，此长度的循环节就不会存在了。
- 证明易证（就是想不到= =）。
- 所以枚举循环节长度，二分消失时间即可。
- 怎么判断一个串是否有(x)长度作为其循环节？
- 判断(s[1...n-x])是否等于(s[x+1...n])即可，证明就是两个串错位相等。
代码实现不是很难，hash预处理即可。
Code
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 5;
typedef unsigned long long ull;
template <unsigned mod, unsigned base>
struct rolling_hash {
unsigned int pg[N], val[N]; // val:1,2...n
rolling_hash() {
pg[0] = 1;
for(int i = 1; i < N; i++) pg[i] = 1ull * pg[i - 1] * base % mod;
val[0] = 0;
}
void build(const char *str) {
for(int i = 0; str[i]; i++) {
val[i + 1] = (str[i] + 1ull * val[i] * base) % mod;
}
}
unsigned int operator() (int l, int r) {
++r;
return (val[r] - 1ull * val[l] * pg[r - l] % mod + mod) % mod;
}
};
struct dm_hasher {
//str:0,1...len-1
rolling_hash<997137961, 753> h1;
rolling_hash<1003911991, 467> h2;
void build(const char *str) {
h1.build(str); h2.build(str);
}
ull operator() (int l, int r) {
return ull(h1(l, r)) << 32 | h2(l, r);
}
}hasher;
int n;
char str[2][10];
vector <pii> pos;
int sum[N];
int checker(int l, int r, int x) {
while(l < r) {
int mid = (l + r) >> 1;
int ll = pos[mid].fi, rr = pos[mid].se;
if(hasher(ll, rr - x) == hasher(ll + x, rr)) l = mid + 1;
else r = mid;
}
return r;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
list <char> ch;
int nl = 0, nr = 0;
pos.push_back(MP(0, 0));
for(int i = 1; i <= n; i++) {
cin >> str[0] >> str[1];
if(str[1][0] == 's' && str[1][1] == 'o') str[1][0] = 'z';
if(str[0][0] == 'a') {
ch.push_front(str[1][0]);
++nl;
} else {
ch.push_back(str[1][0]);
++nr;
}
pos.push_back(MP(nl, nr));
}
hasher.build(string(ch.begin(), ch.end()).c_str());
for(auto &it : pos) it.fi = nl - it.fi, it.se += nl - 1;
for(int i = 1; i <= n; i++) {
sum[i]++;
sum[checker(i + 1, n + 1, i)]--;
}
for(int i = 1; i <= n; i++) sum[i] += sum[i - 1];
for(int i = 1; i <= n; i++) cout << sum[i] << '
';
return 0;
}
D.Han Xin and His Troops
题意：
求解方程组：
[left{
egin{aligned}
&xequiv b_1(\% a_1)\
&xequiv b_2(\% a_2)\
&cdots\
&xequiv b_n(\% a_n)
end{aligned}
ight.
]
其中，(0leq b_i<a_i<10^5)。
如果无解输出(-1)，若解超过了(m)输出(-2)，否则输出最小正整数解。
思路：
直接扩展中国剩余定理可能答案会爆(int128)。
- 注意到当(M>m)时，(x+im,i>0)则超过阀值，那么对于这种情况能存在合法解就只有(i=0)了，所以特判一下即可。
- 但也可能存在无解，无解怎么判断？
- 我是随机化了一波，但实际上直接(O(n^2))枚举即可判断。
代码如下：
Code
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
typedef pair<int, int> pii;
const int N = 105;
ll n, m;
int a[N], b[N];
struct Istream {
template <class T>
Istream &operator >>(T &x) {
static char ch;static bool neg;
for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
x=neg?-x:x;
return *this;
}
}fin;
struct Ostream {
template <class T>
Ostream &operator <<(T x) {
x<0 && (putchar('-'),x=-x);
static char stack[233];static int top;
for(top=0;x;stack[++top]=x%10+'0',x/=10);
for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
return *this;
}
Ostream &operator <<(char ch) {
putchar(ch);
return *this;
}
}fout;
void exgcd(ll a, ll b, ll &x, ll &y) {
if(b == 0) {
x = 1, y = 0;
return ;
}
exgcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - (a / b) * y;
}
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
pii p[N];
int main() {
fin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
p[i] = make_pair(a[i], b[i]);
}
int tot = 1000;
int ok = 1;
while(tot-- && ok != 0) {
random_shuffle(p + 1, p + n + 1);
ll x = p[1].second, M = p[1].first;
for(int i = 2; i <= n; i++) {
ll X, Y, g;
if(M > m) break;
g = gcd(M, (ll)p[i].first);
int c = (p[i].second - x) % p[i].first;
if(c < 0) c += p[i].first;
if(c % g != 0) {
ok = 0; break;
}
exgcd(M / g, p[i].first / g, X, Y);
X = X * c / g;
x = x + X * M;
M = p[i].first / g * M;
x %= M;
if(x < 0) x += M;
if(x > m) break;
}
}
if(ok == 0) {
cout << "he was definitely lying" ;
return 0;
}
ll x = p[1].second, M = p[1].first;
for(int i = 2; i <= n; i++) {
ll X, Y, g;
if(M > m) {
if(x % p[i].first != p[i].second) {
ok = -1; break;
}
continue;
}
g = gcd(M, (ll)p[i].first);
int c = (p[i].second - x) % p[i].first;
if(c < 0) c += p[i].first;
if(c % g != 0) {
ok = 0; break;
}
exgcd(M / g, p[i].first / g, X, Y);
X = X * c / g;
x = x + X * M;
M = p[i].first / g * M;
x %= M;
if(x < 0) x += M;
if(x > m) {
ok = -1;
break;
}
}
if(ok == 1) cout << (long long)x ;
else cout << "he was probably lying";
return 0;
}
E.Hilbert Sort
题意：
对二维坐标((x,y))进行希尔伯特排序。
思路：
递归处理变换即可。
左上角和右上角本质上是关于直线对称，只需要找对称后的坐标即可。
详见代码：
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 6;
int n, k;
struct point{
int x, y;
ll id;
}a[N];
ll gid(int x, int y, int k) {
if(k == 0) return 1;
ll m = 1 << (k - 1);
if(x <= m && y <= m) return gid(y, x, k - 1);
if(x > m && y <= m) return m * m + gid(x - m, y, k - 1);
if(x > m && y > m) return 2 * m * m + gid(x - m, y - m, k - 1);
return 3 * m * m + gid(2 * m - y + 1, 1 + m - x, k - 1);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
a[i].id = gid(a[i].x, a[i].y, k);
}
sort(a + 1, a + n + 1, [&](point A, point B){
return A.id < B.id;
});
for(int i = 1; i <= n; i++) cout << a[i].x << ' ' << a[i].y << '
';
return 0;
}
F.Popping Balloons
题意：
在范围不超过(10^5)的二维平面中，存在一些点。现在你可以竖直方向打三枪，水平方向打三枪，问最多可以打到多少点。
思路：
维护纵坐标信息，直接枚举横坐标，很容易知道会打中哪些点。
接下来考虑加上纵坐标中能打中的最多的点，但可能会重复计算某些点，所以直接暴力修改信息即可。
纵坐标相关信息可以用(multiset)维护，复杂度为(O(9nlogn))。
但实际上可以优化：
因为纵坐标信息中值的减少或增加是连续的，所以可以用一个桶来代替(set)，根据桶的信息来维护最大值即可。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, r;
int x[N], y[N];
int cnt[N], a[N], b[N];
int MAX;
vector <int> v[N];
int gnum(int r) {
if(r < 0 || r >= N) return 0;
return cnt[r];
}
void del(int Y) {
if(Y >= 0 && Y < N) {
b[a[Y]]--;
if(b[a[Y]] == 0 && a[Y] == MAX) MAX--;
b[--a[Y]]++;
}
}
void add(int Y) {
if(Y >= 0 && Y < N) {
b[a[Y]]--; a[Y]++;
if(++b[a[Y]] == 1 && a[Y] - 1 == MAX) MAX++;
}
}
void Del(int p) {
if(p < 0 || p >= N) return;
for(auto it : v[p]) {
del(it - r); del(it); del(it + r);
}
}
void Add(int p) {
if(p < 0 || p >= N) return;
for(auto it : v[p]) {
add(it - r); add(it); add(it + r);
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> r;
for(int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
cnt[y[i]]++; v[x[i]].push_back(y[i]);
}
for(int i = 0; i < N; i++) {
a[i] = gnum(i) + gnum(i - r) + gnum(i + r);
b[a[i]]++;
if(a[i] > MAX) MAX = a[i];
}
for(int i = 0; i < N; i++) cnt[i] = 0;
for(int i = 1; i <= n; i++) cnt[x[i]]++;
int ans = 0;
for(int i = 0; i < N; i++) {
int tmp = gnum(i - r) + gnum(i) + gnum(i + r);
Del(i - r); Del(i); Del(i + r);
ans = max(ans, tmp + MAX);
Add(i - r); Add(i); Add(i + r);
}
cout << ans;
return 0;
}
G.Road Construction
那张图很直观，我就不再搞一次了。
有点不懂为什么平行也是一种情况，有知道的大佬告诉我一下，不胜感激~
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 305;
int n;
int x[N], y[N];
double calc(double k) {
vector <double> res;
for(int i = 1; i <= n; i++) res.push_back(((double)y[i] - k * x[i]) / sqrt(k * k + 1));
sort(res.begin(), res.end());
double ans = double(res[(n - 1) / 2 + 1] - res[(n - 1) / 2]) / 2;
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
double ans = 0;
for(int i = 2; i <= n; i++) {
for(int j = 1; j < n; j++) {
if(x[i] == x[j] || y[i] == y[j]) continue;
double k = (double)(y[i] - y[j]) / (x[i] - x[j]);
ans = max(ans, calc(k));
k = -1.0 / k;
ans = max(ans, calc(k));
}
}
sort(x + 1, x + n + 1);
sort(y + 1, y + n + 1);
ans = max(ans, double(x[n / 2 + 1] - x[n / 2]) / 2.0);
ans = max(ans, double(y[n / 2 + 1] - y[n / 2]) / 2.0);
printf("%.12f", ans);
return 0;
}
H.Stammering Chemists
签到。
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[10];
int mp[10][10];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T;cin>>T;
while(T--){
memset(a,0,sizeof(a));
memset(mp,0,sizeof(mp));
for(int i=0;i<5;i++){
int x,y;cin>>x>>y;
a[x]++,a[y]++;
mp[x][y]=1;
mp[y][x]=1;
}
int a3=0,a4=0,ind=0;
for(int i=1;i<=6;i++){
if(a[i]==3) a3++,ind = i;
if(a[i]==4) a4++;
}
string s = "3-methylpentane";
int sum = 0;
if(a4) {
cout<<"2,2-dimethylbutane"<<'
';
}
else if(!a3) {
cout<<"n-hexane"<<'
';
}
else if(a3==2) {
cout<<"2,3-dimethylbutane"<<'
';
}
else if(a3==1){
for(int i=1;i<=6;i++){
if(mp[i][ind] && a[i]==1) sum++;
}
if(sum==2) s = "2-methylpentane";
cout<<s<<'
';
}
}
return 0;
}
J.Wood Processing
(dp(i,j))表示前i个划分成k段的最小花费，那么转移式子很好写：
[egin{aligned}
dp(i,j)=dp(k,j-1) + (S_i-S_k)-(sumw_i-sumw_k)cdot a[k+1]\
end{aligned}
]
我们将其变一下，转换为斜率(dp)的形式：
[dp(k,j-1)-S_k+sumw_kcdot a_{k+1}=sumw_icdot a_{k+1}+dp(i,j)-S_j
]
我们以(a_{k+1})为(x)，以(dp(k,j-1)-S_k+sumw_kcdot a_{k+1})为(y)，利用队列维护一个下凸壳就行了。因为(sumw_i)是单调不减的，所以可以不用二分。
实现的话可以开(2000)个队列，但其实可以直接滚动掉；另外(dp)数组也可以滚动一维....
我手残啊把(a_{k+1})打成(a_k)调一晚上...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005, K = 2005;
int n, k;
ll sum[N], h[N], sumw[N];
ll dp[N][K], g[N];
int q[N];
struct node{
int h, w;
bool operator < (const node &A) const {
return h < A.h;
}
}a[N];
int main() {
#ifdef heyuhhh
freopen("input.in", "r", stdin);
#else
ios::sync_with_stdio(false); cin.tie(0);
#endif
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i].w >> a[i].h;
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + (ll)a[i].w * a[i].h;
sumw[i] = sumw[i - 1] + a[i].w;
}
for(int i = 1; i <= n; i++) dp[i][1] = sum[i] - a[1].h * sumw[i], g[i] = dp[i][1] - sum[i] + sumw[i] * a[i + 1].h;
for(int j = 2; j <= k; j++) {
int l = 1, r = 1; q[1] = j - 1;
for(int i = j; i <= n; i++) {
while(l < r && g[q[l + 1]] - g[q[l]] <= (__int128)sumw[i] * (a[q[l + 1] + 1].h - a[q[l] + 1].h)) ++l;
dp[i][j] = dp[q[l]][j - 1] + sum[i] - sum[q[l]] - (__int128)(sumw[i] - sumw[q[l]]) * a[q[l] + 1].h;
while(l < r && (__int128)(g[i] - g[q[r]]) * (a[q[r] + 1].h - a[q[r - 1] + 1].h) <= (__int128)(g[q[r]] - g[q[r - 1]]) * (a[i + 1].h - a[q[r] + 1].h)) --r;
q[++r] = i;
}
for(int i = j; i <= n; i++) g[i] = dp[i][j] - sum[i] + sumw[i] * a[i + 1].h;
}
cout << (ll)dp[n][k];
return 0;
}