Identical Somehow
有 1 不可能，其他情况都是 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
const ll N=420+7,mod=1e9+7;
const ll inf=1e18;
const double eps=1e-11;
void solve()
{
ll x,y;
cin>>x>>y;
if(x!=1&&y!=1) printf("1\n");
else {
printf("-1\n");
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T=1;
cin>>T;
while(T--) {
solve();
}
return 0;
}
|
Field of Fire
找到最长的连续 0 ，看为其隔离能留下多少
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
const ll N=5e5+7,mod=998244353;
const ll inf=1e18;
const double eps=1e-11;
void solve()
{
vector<int> a;
string s;
int n,t,st=0,ed=0;
cin>>n>>t>>s;
rep(i,0,n-1){
if(s[i]=='1') {
st=i;
break;
}
}
per(i,n-1,0){
if(s[i]=='1') {
ed=i;
break;
}
}
a.push_back(st+n-1-ed);
int last=st;
rep(i,st+1,ed) {
if(s[i]=='1') {
a.push_back(i-last-1);
last=i;
}
}
sort(a.begin(), a.end(),greater<int>());
bool flag=1;
int ans=0;
for(auto x:a) {
int s=2;
if(flag) s=1,flag=0,--x;
int res=max(0,x-t*s);
ans+=res;
}
printf("%d\n",ans);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T=1;
cin>>T;
while(T--) {
solve();
}
return 0;
}
|
Bitwise Perfect
易发现，操作 x, y 得到的 z 要严格大于 max(x, y)。
0-1 Trie 树满足解法
题解正解为，当数组长度小于 60 时，直接暴力判断，否则一定会小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
const ll N=5e5+7,mod=998244353;
const ll inf=1e18;
const double eps=1e-11;
int tr[N*61][2],tot=0;
ll a[N];
void add(ll x)
{
int now=0;
per(i,60,0) {
int c=(x>>i)&1;
if(!tr[now][c]) tr[now][c]=++tot;
now=tr[now][c];
}
}
bool check(ll x)
{
int now=0;
ll res=0;
per(i,60,0) {
int c=(x>>i)&1;
if(tr[now][c]) now=tr[now][c];
else {
res+=(1LL<<i);
now=tr[now][c^1];
}
}
return res>x;
}
void solve()
{
rep(i,0,tot) tr[i][0]=tr[i][1]=0;
tot=0;
int n;
cin>>n;
rep(i,1,n) cin>>a[i];
sort(a+1,a+1+n);
add(a[1]);
rep(i,2,n) {
bool ans=check(a[i]);
if(!ans) {
printf("NO\n");
return;
}
add(a[i]);
}
printf("YES\n");
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T=1;
cin>>T;
while(T--) {
solve();
}
return 0;
}
|
Another Day of Sun
显然考虑 DP。
定义以下 DP 状态：
- $f[i][j]$：表示所有长度为 $i$，且第 $i$ 位为 $j$（$j \in {0, 1}$）的合法序列的天数总和。
- $cnt[i][j]$：表示所有长度为 $i$，且第 $i$ 位为 $j$（$j \in {0, 1}$）的合法序列的数量。
如果第 $i$ 位填 0 (当 $a_i=0$ 或 $a_i=-1$ 时)：
它可以接在任何一个以 0 或 1 结尾的长度为 $i-1$ 的序列后面。
数量：$cnt[i] = (cnt[i-1] + cnt[i-1]) \pmod{mod}$。
天数总和：因为在末尾添加 0 不会产生新的天数，所以我们只是把之前的天数和继承过来。
$f[i] = (f[i-1] + f[i-1]) \pmod{mod}$。
如果第 $i$ 位填 1 (当 $a_i=1$ 或 $a_i=-1$ 时)：
它也可以接在任何一个以 0 或 1 结尾的长度为 $i-1$ 的序列后面。
数量：$cnt[i] = (cnt[i-1] + cnt[i-1]) \pmod{mod}$。
天数总和：这里是关键。
如果接在以 1 结尾的序列后面（形如 …11），天数不变。这部分贡献的天数总和是 $f[i-1]$。
如果接在以 0 结尾的序列后面（形如 …01），每个这样的序列都会新增 1 天。共有 $cnt[i-1]$ 个这样的序列，所以天数总和会额外增加 $cnt[i-1]$。这部分贡献的天数总和是 $f[i-1] + cnt[i-1]$。
所以总的天数和是：$f[i] = (f[i-1] + f[i-1] + cnt[i-1]) \pmod{mod}$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
const ll N=5e5+7,mod=998244353;
const ll inf=1e18;
const double eps=1e-11;
int f[N][2],a[N],cnt[N][2];
void solve()
{
int n;
cin>>n;
rep(i,1,n) cin>>a[i];
f[0][0]=f[0][1]=0;
cnt[0][0]=1;
cnt[0][1]=0;
rep(i,1,n) {
rep(j,0,1) {
if(!(a[i]==-1||a[i]==j)) continue;
f[i][j]=(f[i-1][0]+f[i-1][1])%mod;
if(j) f[i][j]=(f[i][j]+cnt[i-1][0])%mod;
cnt[i][j]=(cnt[i-1][0]+cnt[i-1][1])%mod;
}
}
printf("%lld\n",(f[n][0]+f[n][1])%mod);
rep(i,1,n) f[i][0]=f[i][1]=cnt[i][0]=cnt[i][1]=0;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T=1;
cin>>T;
while(T--) {
solve();
}
return 0;
}
|
Love Wins All
根据题意，可以推断出，所有居民会构成若干个偶数长度的环，0 个或 2 个的奇数长度环。
需要拆出两个人：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
const ll N=5e5+7,mod=998244353;
const ll inf=1e18;
const double eps=1e-11;
int a[N],cnt=0;
vector<ll> c[2];
ll inv[3];
bool vis[N];
ll qpow(ll x,ll k)
{
ll res=1;
while(k) {
if(k&1) res=res*x%mod;
x=x*x%mod;
k>>=1;
}
return res;
}
void dfs(int x)
{
if(vis[x]) {
c[cnt&1].push_back(cnt);
return;
}
vis[x]=1;
++cnt;
dfs(a[x]);
}
void solve()
{
c[0].clear();
c[1].clear();
int n;
cin>>n;
rep(i,1,n) {
cin>>a[i];
}
rep(i,1,n) {
cnt=0;
if(!vis[i]) dfs(i);
}
rep(i,1,n) {
vis[i]=0;
}
if(c[1].size()>2) {
printf("0\n");
return ;
}
ll ans=0;
if(c[1].size()==2) {
ans=c[1][0]*c[1][1]%mod;
for(auto x:c[0]) {
if(x>2) ans=ans*2%mod;
}
} else {
ans=0;
ll res=1;
for(auto x:c[0]) {
if(x>2) res=res*2%mod;
}
for(auto x:c[0]) {
ll tmp=res;
if(x>2) tmp=tmp*inv[2]%mod;
ll y=(x/2)*(x/2);
ans=(ans+y*tmp%mod)%mod;
}
}
printf("%lld\n",ans);
}
signed main()
{
inv[1]=1;
inv[2]=qpow(2,mod-2);
ios::sync_with_stdio(0);
cin.tie(0);
int T=1;
cin>>T;
while(T--) {
solve();
}
return 0;
}
|
Geometry Friend
太寄把糖了。
当中心点在多边形内时，只要离他最远的点集能覆盖满 360 即可。
当中心点在多边形外时，构成圆环，此时一定要转够 360。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
const double PI = acos(-1.0);
struct Node {
ll x, y;
ll dot(const Node &a) const {
return x * a.x + y * a.y;
}
ll cross(const Node &a) const {
return x * a.y - y * a.x;
}
};
void solve() {
int n;
Node o;
cin >> n >> o.x >> o.y;
vector<Node> p(n + 1);
for (int i = 1; i <= n; i++) {
cin >> p[i].x >> p[i].y;
p[i].x -= o.x;
p[i].y -= o.y;
}
p[0] = p[n];
bool flag = 0;
for (int i = 1; i <= n; i++) {
if (p[i].cross(p[i - 1]) > 0) {
flag = 1;
break;
}
}
if (flag) {
printf("%.10lf\n", 2 * PI);
return;
}
vector<double> ang;
ll mx = 0;
for (int i = 1; i <= n; i++) {
mx = max(mx, p[i].dot(p[i]));
}
for (int i = 1; i <= n; i++) {
if (p[i].dot(p[i]) == mx) {
ang.push_back(atan2(p[i].y, p[i].x));
}
}
sort(ang.begin(), ang.end());
ang.push_back(ang[0] + 2 * PI);
double ans = 0;
for (int i = 1; i < ang.size(); i++) {
ans = max(ans, ang[i] - ang[i - 1]);
}
printf("%.10lf\n", ans);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
Highway Upgrade
观察到题目中提到 $t_j - w_j * k_i > 0$，说明操作一定是集中在一条路上。
那么操作的路的前后都是固定的，可以通过预处理提前得到，对起点终点分别跑 dijkstra，即可得到两侧的 dist。
注意到此时每条路对应的代价 $L_i(k) = \text{dist}(1, u_i) + (t_i - k \cdot w_i) + \text{dist}(v_i, n)$
令 $C_i = \text{dist}(1, u_i) + t_i + \text{dist}(v_i, n)$，那么 $L_i(k) = C_i - w_i \cdot k$。
此时问题转化为 $\min_{i=1 \dots m} { C_i - w_i \cdot k }$，这是一个经典的“查询直线集合在某点上的最小值”问题，每一条边 $i$ 都对应一条直线 $y = -w_i \cdot k + C_i$。
可以通过凸包优化。
把这些直线 $y = C_i - w_i \cdot k$ 画在以 k 为横坐标，L(k) 为纵坐标的平面上，对于任何一个 k 值（一条竖直线），我们要求的最小值，就是这条竖直线与所有 m 条直线交点中，最下方的那一个。把所有这些最下方的点连起来，就形成了一个下凸壳（Lower Convex Hull）。
我们将线段按照截距升序（如果截距相同，按斜率降序）排列。
通过单调栈完成操作。
遍历所有直线，如果当前直线的斜率比栈中最后一个元素的斜率大，那么他下降的就会比已有的线段慢，因为新直连的截距一定比旧的大，这条直线就不再考虑。
反之，找到找到当前直线比旧线低的位置，如果这个位置比旧线战胜他之前的线的位置更早，就踢出旧线，直到无法踢出，或栈为空。
现在这个单调栈中储存的就是我们要的下凸壳。
我们离线所有查询，排序后对下凸壳查询即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
struct Node {
int v;
ll w;
bool operator<(const Node &a) const {
return w > a.w;
}
};
auto dijkstra(int s, int n, vector<Node> e[]) {
vector<ll> dis(n + 1, -1);
priority_queue<pair<int, ll>, vector<pair<int, ll>>, greater<pair<int, ll>>> pq;
dis.assign(n + 1, LLONG_MAX);
dis[s] = 0;
pq.push({s, 0});
while (!pq.empty()) {
auto [u, d] = pq.top();
pq.pop();
if (d > dis[u]) continue;
for (auto &v : e[u]) {
if (dis[v.v] > d + v.w) {
dis[v.v] = d + v.w;
pq.push({v.v, dis[v.v]});
}
}
}
return dis;
}
void solve() {
int n, m;
cin >> n >> m;
vector<Node> e[2][n + 1];
vector<array<ll, 4>> a(m + 1);
for (int i = 1; i <= m; i++) {
int u, v;
ll t, w;
cin >> u >> v >> t >> w;
a[i] = {u, v, t, w};
e[0][u].push_back({v, t});
e[1][v].push_back({u, t});
}
auto dis0 = dijkstra(1, n, e[0]);
auto dis1 = dijkstra(n, n, e[1]);
vector<pair<ll, ll>> line;
for (int i = 1; i <= m; i++) {
auto [u, v, t, w] = a[i];
if (dis0[u] == LLONG_MAX || dis1[v] == LLONG_MAX) {
continue;
}
ll tmp = dis0[u] + t + dis1[v];
line.push_back({tmp, w});
}
sort(line.begin(), line.end());
deque<pair<pair<ll, ll>, ll>> q;
for (auto [x, y] : line) {
if (!q.empty() && q.back().first.second >= y) continue;
ll tmp = 0;
while (!q.empty()) {
tmp = ceil((double)(x - q.back().first.first) / (y - q.back().first.second));
if (tmp <= q.back().second) {
q.pop_back();
} else {
break;
}
}
if (q.empty()) q.push_back({{x, y}, 0});
else q.push_back({{x, y}, tmp});
}
int qq;
cin >> qq;
vector<pair<ll, ll>> ask;
vector<ll> ans(qq + 1);
for (int i = 1; i <= qq; i++) {
int x;
cin >> x;
ask.push_back({x, i});
}
sort(ask.begin(), ask.end());
for (auto [x, i] : ask) {
while (q.size() > 1 && q[1].second <= x) {
q.pop_front();
}
ans[i] = q[0].first.first - q[0].first.second * x;
}
for (int i = 1; i <= qq; i++) {
cout << ans[i] << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
Donkey Thinks…
题目要求
$$\sum h_i - (V - \sum s_i)(\sum d_i)$$显然难以直接实现，注意到 V 的范围极小，只到 500，所以可以枚举 $(V - \sum s_i)$ 部分中的 $S=\sum s_i$，此时，背包中的每个物品的价值都变成了 $h_i-(V-S)d_i$，此时即可进行常规背包。
但是，完全遍历每一个物品，时间复杂度来到了 $O(V * N log N)$，显然面临 TLE 的局面，不难想到，对于每种体积 s 的物品，我们只会在价值前 $k = \left\lfloor\frac{S}{s}\right\rfloor$ 大的物品中背包。
这里使用 nth_element 进行优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n, v;
cin >> n >> v;
vector<ll> h(n + 1), s(n + 1), d(n + 1);
for (int i =1; i <= n; i++) {
cin >> h[i] >> s[i] >> d[i];
}
ll ans = 0;
for (int i = 1; i <= v; i++) {
vector<ll> dp(501, -1e18);
vector<vector<ll>> val(501);
dp[0] = 0;
int lft = v - i;
for (int j = 1; j <= n; j++) val[s[j]].emplace_back(h[j] - d[j] * lft);
for (int j = 1; j <= i; j++) {
int k = min((int)val[j].size(), i / j);
nth_element(val[j].begin(), val[j].begin() + k - 1, val[j].end(), greater<ll>());
for (int l = 0; l < k; l++) {
for (int r = i; r >= j; r--) {
dp[r] = max(dp[r], dp[r - j] + val[j][l]);
}
}
}
ans = max(ans, dp[i]);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|