A . Nucleic Acid Test 二分 + floyd预处理 + 并查集判图联通
题意 ： 城市中有n个建筑，m条双向道路，n个点中有 k 个是核酸检测点，给定核酸有效时间，问从某一个核酸点经过所有城市并回到某一个核酸点的最小速度
思路 ：二分答案，先用floyd预处理出各点对的最短路程，check时分两种情况 ： 1.核算点到非核酸点，这种情况要考虑往返时间是否在有效时间内；2.核酸点到核酸点，这种只要考虑单程时间即可，用并查集维护最后核酸点是否联通，再判一下是否所有非核酸点都可以走到即可
ac代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
using namespace std;
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,mod = 998244353 ;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-8;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
int n,m,k,t;
uLL g[410][410];
int p[N],is[N];
bool st[N];
int find(int x)
{
if(x != p[x]) return p[x] = find(p[x]);
return x;
}
bool check(LL x)
{
int cnt = k;
for(int i = 1;i <= n;i ++) p[i] = i,st[i] = false;
for(int i = 1;i <= n;i ++)
if(is[i])
{
for(int j = 1;j <= n;j ++)
{
if(is[j])
{
if(1.0 * g[i][j] / t <= x && g[i][j] != LNF)
{
int a = find(i),b = find(j);
if(a != b) p[a] = b,cnt --;
}
}
if(2.0 * g[i][j] / t <= x && g[i][j] != LNF) st[j] = true;
}
}
for(int i = 1;i <= n;i ++) if(!st[i]) return false;
return cnt == 1;
}
int main()
{
ios;
cin >> n >> m >> k >> t;
if(t == 0)
{
cout << -1 << endl;
return 0;
}
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
if(i != j) g[i][j] = LNF;
while(m --)
{
int a,b,w;
cin >> a >> b >> w;
g[a][b] = g[b][a] = min(g[a][b],uLL(w));
}
for(int i = 1;i <= k;i ++)
{
int x;
cin >> x;
is[x] = 1;
}
for(int k = 1;k <= n;k ++)
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
g[i][j] = min(g[i][j],g[i][k] + g[k][j]);
LL l = 1,r = 1e12;
while(l < r)
{
LL mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(l == 1e12) l = -1;
cout << l << endl;
return 0;
}
B. Potion(easy version) 思维
题意：有一个试管，两种液体，每次可以用一种药水加满到试管（初始试管可能有其他混合液体）然后混合后倒掉一半，给定一个比例x : y,问是否能配置出此比例的混合液体，如果可以求出最小的注入液体次数
分析：因为每次都可留一半倒掉一半，所以最终x + y 一定是2的整次幂，而最小操作次数就是x + y 的幂数 + 1
ac代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
using namespace std;
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,mod = 998244353 ;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-8;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
int n,m,k,t;
int main()
{
ios;
cin >> t;
while(t --)
{
LL x,y,a,b;
cin >> x >> y >> a >> b;
LL tt = __gcd(x,y);
x /= tt, y /= tt;
LL ans = 0,sum = x + y;
while(sum % 2 == 0 ) sum /= 2,ans ++;
if(sum != 1) ans = -2;
cout << ans + 1 << endl;
}
return 0;
}
F. Angel 思维
题意：有一排洞，有一只兔子藏在其中，我们每次都可以选择一个洞检查，检查完后，兔子可以移动至其位置所临近的两个位置，考虑最坏情况。问最小的能把兔子查出来的检查次数
思路：朴素的想法，我们应该从一头一个个扫过去，但存在一种情况，当我们查第i个洞时，兔子在第i + 1个位置，然后兔子跳向i，我们完美的与它错过，又因为考虑最坏情况，所以我们必会与其错过，可以归纳总结出当我们查的位置和兔子起始位置的编号奇偶性不同时，我们便会与其错过，所以我们先扫过去一边，然后原地再查一次，改变奇偶相同情况，反方向扫回来就好了。但是这样的次数是2n + 1，能不能再少一点呢？我们发现，既然我们可以默认第一次和兔子的奇偶性一定相反，那我们干脆放弃第一格。我们从第二格子开始检查，检查到n-1格，如果和兔子的奇偶性相同，兔子一定会被逼到n - 1的位置。因此我们也不需要在n处检查。我们在n - 1处再检查一次，这样就保证了和兔子的奇偶性相同，接下来顺次检查回第二个格子即可。
ac代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
using namespace std;
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,mod = 998244353 ;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-8;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
int n,m,k,t;
int main()
{
ios;
cin >> n;
if(n == 1) cout << 1 << endl << 1 << endl;
else if(n == 2 || n == 3) cout << 2 << endl << "2 2" << endl;
else
{
cout << 2 * (n - 2) << endl;
for(int i = 2;i <= n - 1;i ++) cout << i << ' ';
for(int i = n - 1;i > 1;i --) cout << i << ' ';
}
return 0;
}
J. Palindrome Reversion 字符串哈希
题意：给定一个字符串，问是否能通过反转一次某个子区间使整体变成回文串
思路：字符串两边对称相同的字符肯定对答案影响，所以先缩减范围，直至字符串两端字符不同，因为这是从两边看第一次不同的位置，所以两端肯定有且仅有一端是要反转的区间的一段，一端固定了，那么我们就可以线性枚举另一个端点，判断反转后是否回文，判断用字符串哈希 $ o(1) $ 判断即可
ac代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
using namespace std;
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,P = 13331,mod = 998244353 ;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-8;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
int n,m,k,t;
int main()
{
ios;
string s;
cin >> s;
int l = 0,r = s.size() - 1;
while(l < r && s[l] == s[r]) l ++, r --;
if(l >= r) cout << 1 << ' ' << 1 << endl;
else
{
s = s.substr(l,r - l + 1);
n = s.size(), s = ' ' + s;
l ++ , r ++;
vector<uLL> pre(n + 1),suf(n + 2),p(n + 1);
p[0] = 1;
for(int i = 1;i <= n;i ++)
{
pre[i] = pre[i - 1] * P + s[i];
p[i] = p[i - 1] * P;
}
for(int i = n;i;i --)
{
suf[i] = suf[i + 1] * P + s[i];
}
int v = 0;
for(int i = 2;i <= n;i ++)
{
uLL x1 = (suf[1] - suf[i + 1] * p[i]) * p[n - i] + pre[n] - pre[i] * p[n - i];
uLL x2 = pre[i] + suf[i + 1] * p[i];
if(x1 == x2) v = i;
}
if(v)
{
cout << l << ' ' << l + v - 1 << endl;
return 0;
}
for(int i = n - 1;i;i --)
{
uLL x1 = pre[i - 1] * p[n - i + 1] + suf[i];
uLL x2 = suf[1] - suf[i] * p[i - 1] + (pre[n] - pre[i - 1] * p[n - i + 1]) * p[i - 1];
if(x1 == x2) v = i;
}
if(v) cout << l + v - 1 << ' ' << r << endl;
else cout << "-1 -1" << endl;
}
return 0;
}
K. PTT 模拟
题意：求一分段函数
| Score | Score Modifier |
|---|---|
| ≥10000000 | 2.0 |
| 9800000−9999999 | 1.0+(Score−9800000)/200000 |
| ≤9800000 | (Score−9500000)/300000 |
注意值为负时取0
ac代码
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long LL;
int n,m,k,t;
int main()
{
ios;
cin >> t;
while(t --)
{
LL x;
double c;
cin >> x >> c;
if(x >= 10000000) c += 2;
else if(x > 9800000) c += 1.0 + 1.0 * (x - 9800000) / 200000;
else c += 1.0 * (x - 9500000) / 300000;
cout << fixed << setprecision(8) << max(c,0.0) << endl;
}
return 0;
}
Chtholly and the Broken Chronograph 线段树
线段树求sum的板子，加了一个限制条件，即区间加值时，每个元素中状态为0的不加，这个用一个变量标记区间内1的个数即可，灰常简单
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long LL;
const int N = 100010;
int n,m,k,t;
int a[N],s[N];
struct node
{
int l,r;
LL sum,add;
int now;
}tr[N << 2];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
tr[u].now = tr[u << 1].now + tr[u << 1 | 1].now;
}
void pushdown(node & u,LL add)
{
u.sum += u.now * add;
u.add += add;
}
void pushdown(int u)
{
if(tr[u].add)
{
pushdown(tr[u << 1],tr[u].add);
pushdown(tr[u << 1 | 1],tr[u].add);
tr[u].add = 0;
}
}
void build(int u,int l,int r)
{
if(l == r)
{
tr[u] = {l,r,a[r],0,s[r]};
return ;
}
tr[u] = {l,r,0,0,0};
int mid = l + r >> 1;
build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
pushup(u);
}
void modify(int u,int l,int r,int v)
{
if(tr[u].l >= l && tr[u].r <= r)
{
pushdown(tr[u],v);
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1,l,r,v);
if(r > mid) modify(u << 1 | 1,l,r,v);
pushup(u);
}
void modify(int u,int x)
{
if(tr[u].l == tr[u].r)
{
tr[u].now = 1 - tr[u].now;
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u << 1,x);
else modify(u << 1 | 1,x);
pushup(u);
}
LL query(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL res = 0;
if(l <= mid) res += query(u << 1,l,r);
if(r > mid) res += query(u << 1 | 1,l,r);
return res;
}
int main()
{
ios;
cin >> n >> t;
for(int i = 1;i <= n;i ++) cin >> a[i];
for(int i = 1;i <= n;i ++) cin >> s[i];
build(1,1,n);
while(t --)
{
int op;
int x,l,r;
cin >> op;
if(op == 1 || op == 2)
{
cin >> x;
modify(1,x);
}
else if(op == 3)
{
cin >> l >> r >> x;
modify(1,l,r,x);
}
else
{
cin >> l >> r;
cout << query(1,l,r) << endl;
}
// cout << "now : "<< tr[1].now << endl;
}
return 0;
}