2018ACM四川省省赛
5小时训练赛过9题
然后上周刚刚结束的2021年四川省赛同样9题拿金了，好耶，差两名拿季军奖杯Orz
A. Angel Beats
Problem
Solution
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+2;
bitset<maxn>dp[maxn],sum[maxn],ans;
void solve()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;i <= n+1;++i){
sum[i].reset();
dp[i].reset();
}
for(int i = n;i >= 1;--i){
dp[i].set(i);
for(int j = i+i;j <= n;j += i){
dp[i] ^= dp[j];
}
sum[i] = dp[i]^sum[i+1];
}
ans.reset();
for(int i = 1,a,b;i <= m;++i){
scanf("%d%d",&a,&b);
ans ^= sum[a]^sum[b+1];
printf("%d\n",ans.count());
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
solve();
}
}
B. Beyond the Boundry
Problem
Solution
暴力即可。
Code
#include <bits/stdc++.h>
using namespace std;
string ss[4] = {
"Kanbara Akihito", "Kuriyama Mirai","Nase Hiroomi","Nase Mitsuki"};
bool check(string a, string b)
{
int i = 0;
int j = 0;
while(i < (int)a.size() && j < (int)b.size()){
if(b[j] == a[i]){
i++;
}
j++;
}
return i == (int)a.size();
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
string s;
cin>>s;
vector<string> tmp;
for(int i = 0;i < 4;++i){
if(check(s,ss[i])) tmp.push_back(ss[i]);
}
printf("%d\n",(int)tmp.size());
for(auto it : tmp) cout << it << endl;
}
return 0;
}
C. Clannad
Problem
Solution
AC自动机上DP即可。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9+7;
const int maxn = 1e5+5;
struct ACAM
{
int tree[maxn][26],fail[maxn],last[maxn],tot,end[maxn],len[maxn];
ll dp[maxn];
void init()
{
memset(dp,0,sizeof(dp));
dp[0] = 1;
tot = 0;
memset(tree,0,sizeof(tree));
memset(fail,0,sizeof(fail));
memset(last,0,sizeof(last));
memset(end,0,sizeof(end));
memset(len,0,sizeof(len));
}
void Insert(const char *s){
int root = 0;
int l = 0;
for(int i = 0;s[i];++i){
int p = s[i]-'a';
l++;
if(!tree[root][p]){
tree[root][p] = ++tot;
len[tot] = l;
}
root = tree[root][p];
}
end[root] = 1;
}
void get_fail(){
queue<int> q;
for(int i = 0;i < 26;++i){
if(tree[0][i])
q.push(tree[0][i]);
}
while(!q.empty()){
int now = q.front();
q.pop();
last[now] = end[fail[now]]?fail[now]:last[fail[now]];
for(int i = 0;i < 26;++i){
if(tree[now][i]){
q.push(tree[now][i]);
fail[tree[now][i]] = tree[fail[now]][i];
}
else tree[now][i] = tree[fail[now]][i];
}
}
}
void solve(const char*s,int n){
int root = 0;
for(int i = 1;i <= n;++i){
root = tree[root][s[i]-'a'];
int tmp = root;
if(end[root]){
dp[i] += dp[i-len[root]];
dp[i] %= mod;
}
tmp = last[tmp];
while(tmp){
dp[i] += dp[i-len[tmp]];
dp[i] %= mod;
tmp = last[tmp];
}
printf("%lld%c",dp[i],i==n?'\n':' ');
}
}
}ac;
char s[maxn],t[maxn];
void solve()
{
ac.init();
int n,q;
scanf("%d%d",&n,&q);
scanf("%s",s+1);
for(int i = 1;i <= q;++i){
scanf("%s",t);
ac.Insert(t);
}
ac.get_fail();
ac.solve(s,n);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
solve();
}
}
// 9 5
// zzbzzbcbb
// zz
// z
// zb
// cb
// b
D. Darling in the Franxx
Problem
Solution
首先以 1 为根进行 dfs ，记录一下祖先信息，dfs序。对于任意两个点若他们不是祖先关系则只有当他们的子树上的点为根时才能满足祖先关系。若是祖先关系，则他们路径上的点及其所有子节点都不能作为根。因为一个点的子树上的点的dfs序都是连续的所以对子树上的点打标记用差分即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int LGS = 18;
vector<int> edge[maxn];
int dfn[maxn],rnk[maxn],dfn_clock;
int l[maxn],r[maxn];
int son[maxn],dep[maxn];
int fa[maxn][20];
int val[maxn];
void dfs(int now,int pre)
{
l[now] = ++dfn_clock;
dep[now] = dep[pre]+1;
fa[now][0] = pre;
for(int i = 1;i <= LGS;++i){
fa[now][i] = fa[fa[now][i-1]][i-1];
}
for(auto &x:edge[now]){
if(x==pre)continue;
dfs(x,now);
}
r[now] = dfn_clock;
}
int lca(int x,int y)
{
if(dep[x] < dep[y])swap(x,y);
for(int i = LGS;i >= 0;--i){
if(dep[fa[x][i]] >= y)x = fa[x][i];
}
for(int i = LGS;i >= 0;--i){
if(fa[x][i]!=fa[y][i]){
x = fa[x][i];
y = fa[y][i];
}
}
if(x!=y)return fa[x][0];
return x;
}
void init()
{
dfn_clock = 0;
memset(son,0,sizeof(son));
memset(val,0,sizeof(val));
}
void solve()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i)edge[i].clear();
init();
for(int i = 1,a,b;i < n;++i){
scanf("%d%d",&a,&b);
edge[a].push_back(b);
edge[b].push_back(a);
}
dfs(1,0);
for(int i = 1,a,b;i <= m;++i){
scanf("%d%d",&a,&b);
int g = lca(a,b);
if(dep[a] > dep[b])swap(a,b);
if(g==a){
int x = b;
for(int i = LGS;i >= 0;--i){
if(dep[fa[x][i]]>dep[g])x = fa[x][i];
}
val[1]++;
val[l[x]]--,val[r[x]+1]++;
val[l[b]]++,val[r[b]+1]--;
}
else{
val[l[a]]++,val[r[a]+1]--;
val[l[b]]++,val[r[b]+1]--;
}
}
int ans = 0;
for(int i = 1;i <= n;++i){
val[i] += val[i-1];
ans += val[i]==m;
}
printf("%d\n",ans);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}
E. Ever17
Problem
Solution
模拟即可，注意 01/01/01 和 01/01/01 是同一天，所以要输出 January 1, 2001，因为是同一天。
Code
#include <bits/stdc++.h>
using namespace std;
string s[13] = {
"","January","February","March","April","May","June","July","August","September","October","November","December"};
int day[13] = {
0,31,28,31,30,31,30,31,31,30,31,30,31};
int addone(int y)
{
if(y % 4 == 0) return 1;
return 0;
}
bool check1(int a,int b,int c)
{
if(a > 12 || a < 1) return 0;
if(b < 1 || b > day[a] + (a == 2 ? addone(c) : 0)) return 0;
return 1;
}
int calc(vector<int> a, vector<int> b)
{
if(a > b) swap(a,b);
int cnt = 0;
while(a != b){
a[2]++;
if(a[2] > day[a[1]] + (a[1] == 2 ? addone(a[0]) : 0) ) a[2] = 1,a[1]++;
if(a[1] == 13) a[1] = 1,a[0]++;
cnt++;
}
return cnt;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int a,b,c;
scanf("%d/%d/%d",&a,&b,&c);
vector<int> x,y;
if(check1(a,b,c)) x.push_back(c),x.push_back(a),x.push_back(b);
if(check1(b,c,a)) y.push_back(a),y.push_back(b),y.push_back(c);
if(x.size() && y.size() && x != y){
int cnt = calc(x,y);
printf("%d\n",cnt);
continue;
}
if(x.size()){
cout<<s[x[1]];
printf(" %d, 20%02d\n",x[2],x[0]);
continue;
}
if(y.size()){
cout<<s[y[1]];
printf(" %d, 20%02d\n",y[2],y[0]);
continue;
}
}
return 0;
}
F. Fullmetal Alchemist
Problem
Solution
考虑 O ( n 2 ) O(n^2) O(n2) 枚举子区间，枚举的同时维护对顶堆，复杂度 O ( T ∗ n 2 ∗ l o g n ) O(T*n^2*logn) O(T∗n2∗logn)
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2005;
using ll = long long;
int a[maxn];
ll sum[maxn];
ll ans[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n;
memset(ans,0,sizeof(ans));
scanf("%d",&n);
for(int i = 1;i <= n;++i){
scanf("%d",&a[i]);
sum[i] = sum[i-1]+a[i];
}
for(int i = 1;i <= n;++i){
priority_queue<int,vector<int>,greater<int>> mx;
priority_queue<int,vector<int>,less<int>> mi;
bool now = 1;
ll add = 0;
for(int j = i;j <= n;++j){
if(now){
if(mi.empty())mi.push(a[j]),add+=a[j];
else{
int tmp = mx.top();
if(a[j] > tmp){
mx.pop();
mx.push(a[j]);
mi.push(tmp);
add += tmp;
}
else {
mi.push(a[j]);
add += a[j];
}
}
}
else{
int tmp = mi.top();
if(a[j] < tmp){
mi.pop();
mi.push(a[j]);
mx.push(tmp);
add -= tmp-a[j];
}
else {
mx.push(a[j]);
}
ans[(j-i+1)/2] = max(ans[(j-i+1)/2],sum[j]-sum[i-1]-add-add);
// cout<<i<<' '<<j<<' '<<add<<' '<<sum[j]-sum[i-1]-add-add<<endl;
}
now = !now;
}
}
for(int i = 1;i <= n/2;++i)printf("%lld%c",ans[i],(i==n/2?'\n':' '));
}
return 0;
}
G. Grisaia
Problem
计算：
a n s = ∑ i = 1 n ∑ j = 1 i ( n m o d ( i × j ) ) ans =\sum^n_{i=1}\sum^i_{j=1} (n\ mod (i \times j)) ans=i=1∑nj=1∑i(n mod(i×j))
其中 t ≤ 5 , n ≤ 1 0 11 t\le 5, n\le 10^{11} t≤5,n≤1011
Solution
使用模的展开式将上述和式展开后，显然枚举 k = i × j k=i\times j k=i×j，由于 n ≤ 1 0 11 n\le10^{11} n≤1011，杜教筛即可。
筛出：
f ( x ) = x × ∑ i ∣ k 1 g ( x ) = x × μ ( x ) f(x)=x\times \sum\limits_{i|k} 1\\g(x)=x \times \mu(x) f(x)=x×i∣k∑1g(x)=x×μ(x)
然后整除分块即可。
详解见这里：https://blog.csdn.net/weixin_45697774/article/details/117172503
附训练赛时草稿纸一份：
这里是杜教筛筛出来 g ( x ) = x × μ ( x ) g(x)=x\times \mu(x) g(x)=x×μ(x)：
注意 n ≤ 1 0 11 n\le10^{11} n≤1011，中间多处会爆 long long，强转成 __int128 即可。
（因为这个wa了8发hhh，五颜六色的）
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
const int N = 31644346;
int n, m;
int mu[N];
int primes[N], cnt;
int d[N];
int num[N];
unordered_map<int, ll> sum_mui;
unordered_map<int, ll> sum_dk;
bool vis[N];
int sum[N];
inline ll read()
{
register ll x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c-48,c = getchar();
return x * f;
}
inline void print(ll x)
{
if(x < 10)
{
putchar(x + 48);
return;
}
print(x / 10), print(x % 10);
}
void init(int n)
{
vis[0] = vis[1] = 1;
mu[1] = d[1] = 1;
for(int i = 2; i <= n; ++ i) {
if(vis[i] == 0) {
primes[ ++ cnt] = i;
mu[i] = -1;
d[i] = 2 * i;
num[i] = 1;
}
for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
vis[i * primes[j]] = 1;
if(i % primes[j] == 0) {
mu[i * primes[j]] = 0;
num[i * primes[j]] = num[i] + 1;
d[i * primes[j]] = (ll)d[i] / num[i * primes[j]] * (num[i * primes[j]] + 1) * primes[j];
break;
}
mu[i * primes[j]] -= mu[i];
num[i * primes[j]] = 1;
d[i * primes[j]] = d[i] * d[primes[j]];
}
}
for(int i = 1; i <= n; ++ i) {
sum[i] = sum[i - 1] + mu[i] * i;
d[i] = d[i - 1] + d[i];
}
}
inline ll get_sum_mui(int x)
{
if(x <= N - 7) return sum[x];
if(sum_mui.find(x) != sum_mui.end()) return sum_mui[x];
ll ans = 1;
for(ll l = 2, r; l <= x; l = r + 1) {
r = x / (x / l);
ans -= (ll)(r - l + 1) * (l + r) / 2 * get_sum_mui(x / l);
}
return sum_mui[x] = ans;
}
inline ll get_sum_dk(ll x)
{
if(x <= N - 7) return d[x];
if(sum_dk.find(x) != sum_dk.end()) return sum_dk[x];
ll ans = x * (x + 1) / 2;
for(ll l = 2, r; l <= x; l = r + 1) {
r = x / (x / l);
ans -= (ll)(get_sum_mui(r) - get_sum_mui(l - 1)) * get_sum_dk(x / l);
}
return sum_dk[x] = ans;
}
ll cal(ll x)
{
ll limit = sqrt(x + 0.99);
ll more = limit * (limit + 1) * (2 * limit + 1) / 6;
return (get_sum_dk(x) + more) / 2;
}
void solve()
{
ll ans = (ll)n * n * (n + 1) / 2;
for(ll l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
//cout << "ok" << cal(r) - cal(l - 1) * (n / l) << endl;
ans -= (ll)(cal(r) - cal(l - 1)) * (n / l);
}
print(ans);
puts("");
}
signed main()
{
int t;
init(N - 7);
t = read();
while(t -- ) {
n = read();
solve();
}
return 0;
}
H. Harmony
Problem
给你 a , b a,b a,b，你自己选一个 c c c，使得 a + b + gcd ( a , b , c ) a + b + \gcd(a, b, c) a+b+gcd(a,b,c) 最大，输出这个最大的 a + b + gcd ( a , b , c ) a + b + \gcd(a, b, c) a+b+gcd(a,b,c)
Solution
显然 c = gcd ( a , b ) c=\gcd(a,b) c=gcd(a,b) 时， a + b + gcd ( a , b , c ) a + b + \gcd(a, b, c) a+b+gcd(a,b,c) 最大
Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",a + b + __gcd(a,b));
}
return 0;
}
I. Island
Problem
Solution
根据题意直接 dfs 即可
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5+5;
ll dp[maxn];
ll sum = 0;
ll val[maxn];
vector<int> edge[maxn];
ll ans;
void dfs(int now,int pre)
{
dp[now] = val[now];
ll mx = 0;
for(auto &x:edge[now]){
if(x==pre)continue;
dfs(x,now);
dp[now] += dp[x];
mx = max(mx,dp[x]);
}
mx = max(mx,sum-dp[now]);
ans = min(ans,mx);
}
void solve()
{
int n;
scanf("%d",&n);
for(int i = 1;i <= n;++i)edge[i].clear();
sum = 0;
for(int i = 1;i <= n;++i)scanf("%lld",&val[i]),sum += val[i];
for(int i = 1,a,b;i < n;++i){
scanf("%d%d",&a,&b);
edge[a].push_back(b);
edge[b].push_back(a);
}
ans = 1e18;
dfs(1,0);
printf("%lld\n",ans);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}
J. JoJo’s Bizarre Adventure
Problem
Translation
jojo 有一个长度为 n n n 的 a a a 数组，其中保证 a 0 = 0 a_0=0 a0=0，且 0 = a 1 ≤ a 2 ≤ ⋅ ⋅ ⋅ ≤ a n 0 = a_1 ≤ a_2 ≤ · · · ≤ a_n 0=a1≤a2≤⋅⋅⋅≤an，jojo 构造出了一个多重集： S m u l t i = { a i + a j ∣ 1 ≤ i < j ≤ n } S_{multi} = \{a_i+a_j |1 ≤ i < j ≤ n\} Smulti={ ai+aj∣1≤i<j≤n}，其中保证 S m u l t i S_{multi} Smulti 非严格单调递增。
Dio 想要最少需要知道多少个 S m u l t i S_{multi} Smulti 里的元素，就可以推断出原序列 a a a。
T ≤ 10 , n ≤ 500 , S m u l t i . s i z e = n ( n − 1 ) 2 T\le 10,n\le 500,S_{multi}.size=\cfrac{n(n-1)}{2} T≤10,n≤500,Smulti.size=2n(n−1)
Solution
题太难理解了…
读懂题之后直接模拟即可…
注意特判…
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int a[N];
unordered_map<int,int> mp;
int main()
{
int t;
scanf("%d",&t);
while(t--){
mp.clear();
int n;
scanf("%d",&n);
vector<int> res;
int m = n * (n-1) / 2;
for(int i = 1;i <= m;++i){
scanf("%d",&a[i]);
}
if(n == 1){
puts("0");
continue;
}
if(n == 2){
puts("1");
continue;
}
if(n == 3){
puts("2");
continue;
}
res.push_back(0);
res.push_back(a[1]);
res.push_back(a[2]);
// mp[a[1]] = 0, mp[a[2]] = 1;
mp[a[1] + a[2]] = 1;
int cnt = 2;
for(int i = 3;i <= m;++i){
if(mp[a[i]]) {
mp[a[i]]--;
continue;
}
for(int j = 1;j < res.size();++j) {
mp[a[i] + res[j]]++;
}
res.push_back(a[i]);
if((int)res.size() == n){
cnt = i;
break;
}
}
printf("%d\n",cnt);
}
return 0;
}
K. Kanon
Problem
Solution
Code
转载：https://blog.csdn.net/weixin_45697774/article/details/117089776
查看评论