题目
E
题意
就是给长度为1e5的大小为[0,$2^{18}$)的一个序列，要你求任意1~n个数异或的最大值，首先很容易发现当i=18的时候肯定已经是最大了，就是任意18个数异或已经是最大了，因为范围是[0,2^18)很显然，我1~18个数肯定会异或出尽量多的1，然后之后就是$a[i+2]=a[i]$即可，但是前18个我们怎么求呢，我们可以用卷积，只不过这里是异或卷积。暴力求卷积的话复杂度是$O(n^2logn)$的，所以用FWT快速沃尔什变换来写，与FFT的思想是差不多的，都是分治。不过重新定义了运算，这样就能$O(nlog^2n)$的复杂度解决了，总复杂度就是$O(n+wlog^2w)$
代码实现
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
106
107
108
109
110
111
112
| #include<bits/stdc++.h>
using namespace std;
const int P = 998244353;
void add(int &x, int y) {
(x += y) >= P && (x -= P);
}
void sub(int &x, int y) {
(x -= y) < 0 && (x += P);
}
struct FWT {
int extend(int n) {
int N = 1;
for (; N < n; N <<= 1);
return N;
}
void FWTor(std::vector<int> &a, bool rev) {
int n = a.size();
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
if (!rev) add(a[i + j + m], a[i + j]);
else sub(a[i + j + m], a[i + j]);
}
}
}
void FWTand(std::vector<int> &a, bool rev) {
int n = a.size();
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
if (!rev) add(a[i + j], a[i + j + m]);
else sub(a[i + j], a[i + j + m]);
}
}
}
void FWTxor(std::vector<int> &a, bool rev) {
int n = a.size(), inv2 = (P + 1) >> 1;
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
int x = a[i + j], y = a[i + j + m];
if (!rev) {
a[i + j] = (x + y) % P;
a[i + j + m] = (x - y + P) % P;
} else {
a[i + j] = 1LL * (x + y) * inv2 % P;
a[i + j + m] = 1LL * (x - y + P) * inv2 % P;
}
}
}
}
std::vector<int> Or(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTor(a1, false);
a2.resize(N), FWTor(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTor(A, true);
return A;
}
std::vector<int> And(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTand(a1, false);
a2.resize(N), FWTand(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTand(A, true);
return A;
}
std::vector<int> Xor(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTxor(a1, false);
a2.resize(N), FWTxor(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTxor(A, true);
return A;
}
} fwt;
const int N = 1<<18;
int main() {
int n;
scanf("%d", &n);
vector<int>ans(n);
std::vector<int> a1(N), a2(N);
int mx = 0;
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
mx=max(mx,x);
a1[x]++;
a2[x]++;
}
ans[0]=mx;
int cnt = 1;
std::vector<int> A;
for(int j=1;j<min(21,n);j++) {
A = fwt.Xor(a1, a2);
for(int i=N-1;i>=0;i--)
if(A[i]){
ans[cnt++]=i;
break;
}
for(int i=0;i<N;i++)a1[i]=A[i];
}
for(int i=2;i<n;i++){
ans[i]=max(ans[i-2],ans[i]);
}
for(int i=0;i<n;i++){
printf("%d ",ans[i]);
}
return 0;
}
|
B
题意
给n个点，求一个过原点的圆，使得这个圆上的点数最多。
思路
三点确定一个圆，已经有原点了，再需要两个点，所以暴力枚举两个点，然后可以得到n^2个圆心，然后对这n^2个圆心排序去重，重复的个数为num，则答案为$C_{ans}^2 = num$,因为任意选圆上的两点都可以这个圆心。
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define INF 0x3f3f3f3f
#define PI acos(-1)
long double x[2005],y[2005];
struct point
{
long double x0,y0;
};
long double a,b,c,d,e,f,kkx,kky,kx,ky;
int maxn,kcnt,cnt;
vector<point>p;
point work;
void init(int k1,int k2)
{
if((-y[k1])*(x[k2]-x[k1])-(y[k2]-y[k1])*(-x[k1])!=0)
{
a=2*(x[k2]-x[k1]);
b=2*(y[k2]-y[k1]);
c=x[k2]*x[k2]+y[k2]*y[k2]-x[k1]*x[k1]-y[k1]*y[k1];
d=2*(-x[k2]);
e=2*(-y[k2]);
f=-x[k2]*x[k2]-y[k2]*y[k2];
work.x0=(b*f-e*c)/(b*d-e*a);
work.y0=(d*c-a*f)/(b*d-e*a);
p.push_back(work);
}
}
int cmp(point ka,point kb)
{
if(ka.x0==kb.x0) return ka.y0<kb.y0;
else return ka.x0<kb.x0;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n;
maxn=0;
cnt=0;
kcnt=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x[i]>>y[i];
}
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
init(i,j);
sort(p.begin(),p.end(),cmp);
for(int i=0;i<p.size();i++)
{
if(kcnt==0)
{
kcnt=1;
kx=p[i].x0;
ky=p[i].y0;
}
else
{
if(p[i].x0==kx&&p[i].y0==ky) kcnt++;
else
{
if(kcnt>maxn)
{
maxn=kcnt;
kkx=kx;
kky=ky;
}
kcnt=1;
kx=p[i].x0;
ky=p[i].y0;
}
}
}
int sum;
if(kcnt>maxn)
{
kkx=kx;
kky=ky;
maxn=kcnt;
}
cnt=1;
while(cnt*(cnt-1)/2!=maxn)cnt++;
if(cnt==0) cout<<"1"<<endl;
else cout<<cnt<<endl;
return 0;
}
|
C
题意
给出一棵数，找出最少链覆盖整棵树的边
思路
图论的知识欠缺，只知道有个结论，并且数据好像还水了。
正解应该是先找重心，这里重心的定义是以叶子节点为个数来找，跟普通的找中心方式不同，然后根据重心dfs找出dfs序，叶子节点根据dfs序来排序最后得到一个序列，答案就是1~n/2+1,2~n/2+2这样配对即可。
同校奆用了一种较为繁琐但是我感觉是正确的方法，对一个节点的子节点，如果子节点的叶子节点个数为偶数个，那么保留2个，如果为奇数个，那么保留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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int const N=2e5+10;
int const INF=2e6;
vector<int>f[N];
int minl=INF,ans,n,tot=0,father[N],sz[N],dp[N],num[N];
void dfs(int u,int fa){
sz[u]=1;
for (int i=0;i<f[u].size();i++){
int j=f[u][i];
if (j==fa) continue;
dfs(j,u);
sz[u]+=sz[j];
dp[u]=max(dp[u],sz[j]);
}
dp[u]=max(dp[u],n-sz[u]);
if (minl>dp[u]){
minl=dp[u];
ans=u;
}
}
void dfs2(int u,int fa){
if (f[u].size()==1) num[++tot]=u;
father[u]=fa;
for (int i=0;i<f[u].size();i++){
int j=f[u][i];
if (j==fa) continue;
dfs2(j,u);
}
}
int main(){
scanf("%d",&n);
if (n==1){
printf("0\n");
return 0;
}
int x,y;
for (int i=1;i<n;i++){
scanf("%d%d",&x,&y);
f[x].push_back(y);
f[y].push_back(x);
}
dfs2(1,0);
printf("%d\n",(tot+1)/2);
for (int i=1;i<=(tot+1)/2;i++)
printf("%d %d\n",num[i],num[tot/2+i]);
return 0;
}
|
F
题意
给一个矩阵，$martix_ij=lcm(i,j)$,然后给一个k，要你求k*k的子矩阵的最大值之和，也就是
$\sum_{i=k}^{n}\sum_{j-k}^{m}max(martix_{[i-k+1\dots i][j-k+1\dots i]})$
正解感觉应该是单调队列(但是我不会)，但是根据lcm的性质可以判断出来的是已当前点(x,y)为右下角的子矩阵的最大值应该分布在
(x-5~x,y-5~y)这个区间（不会证明），大概就是如果x与y互质，在判断x与y-1是否互质，大概想一下感觉可行···。然后就确定一个区间暴力冲就好了。打表的时候要根据对称性，不然会T
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<vll>
#define pii pair<int,int>
#define pll pair<ll>
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const int N = 5e3+10;
int a[N][N];
bool vis[N][N];
int main(){
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=5000;i++){
for(int j=i;j<=5000;j++){
a[i][j]=lcm(i,j);
a[j][i]=a[i][j];
}
}
ll ans = 0;
for(int i=k;i<=n;i++){
for(int j=k;j<=m;j++){
if(k==1){
ans+=a[i][j];
continue;
}
if(a[i][j]==i*j)ans+=a[i][j];
else{
ll mm = 0;
for(int x=i-min(k,10)+1;x<=i;x++){
for(int y=j-min(k,10)+1;y<=j;y++){
mm = max(1ll*a[x][y],mm);
}
}
ans+=mm;
}
}
}
printf("%lld\n",ans);
}
|
J
题意
给一个序列{A},问从{1,2,3,4,5,6,….,n}这个序列经过P的置换规则恰巧k次得到A，求这个P序列的置换规则。
再直白点就是P序列的意义是得到一个规则a[i]=a[p[i]]这样不断的置换a一开始为{1,2,3,4,5,7…..n}
这道题可以说是群论的知识(离散没学好，雾)，首先置换其实就是几个环再不停的挪动，例如有一个置换规则P｛2，3，1｝,｛2，3，1｝成一个环,｛1，2，3｝置换第一次
a[1]=a[2],a[2]=a[3],a[3]=a[1] => {2,3,1} 实际上就是把1，2，3的1放到了末尾，也就是把第一个放到了最后一个去，也就是整体左移了。
很显然，如果置换size(环的大小)次，那么环就会恢复原状了，
就是说，只有(0,size)的置换是有效的，但问题是我们要置换k次得到A。
思路
置换k次得到A，然后置换size次为原本的，我们可以把每个环看成一个模群，即%size的一个群，然后求k在该模群下的逆元，也就是
$k^{-1}$，A置换$k^{-1}$次就是P，因为$p\times k=A所以A\times k^{-1}=p$,正向置换是环向左移位，所以反向就是环向右移位。
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<vll>
#define pii pair<int,int>
#define pll pair<ll>
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
int mod;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const int N = 2e5+10;
vector<vector<int>>arc;
int a[N];
int b[N];
bool vis[N];
vector<int>tmp;
void getarc(int s){
while(!vis[s]){
vis[s]=1;
tmp.push_back(s);
s=a[s];
}
}
int main(){
ll n,k;
scanf("%lld %lld",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
if(!vis[a[i]]){
if(a[i]==i){
vis[a[i]]=1;
b[i]=i;
continue;
}
getarc(a[i]);
arc.push_back(tmp);
tmp.clear();
}
}
for(int i=0;i<arc.size();i++){
int len = arc[i].size();
mod=len;
ll in,in1;
exgcd(k,len,in,in1);
in=(in+len)%len;
for(int j=0;j<arc[i].size();j++){
b[arc[i][j]]=arc[i][(j+in)%mod];
}
}
for(int i=1;i<=n;i++){
printf("%d ",b[i]);
}
}
|
G
题意
给两个数组，一个长度为n的A，一个长度为m的B，询问在A上有多少长度为m的区间都满足$A_i>=B_i$
思路
用m的数据范围有40000，想到用bitset，每个$A_i$元素对应一个长度为m的bitset，如果$A_i>B_j$那么$bitset_i[j]=1$，例如样例中的
6 3
1 4 2 8 5 7
2 3 3
1-> 000
4->111
2->100
如果暴力遍历O(n)求bitset显然超时，但是注意到对应的bitset只有m个不同的。如果把这m个不同的bitset处理出来，每个$A_i$对应的bitset用$logm$的复杂度来找。
如何处理处m个不同的bitset？我们对B数组从小到大排序，然后遍历B，对当前遍历到的位置进行置为1即可。
然后我们再来看问题，设n个长度为m的bitset，记为$cur_i$，$cur[j]=1$的含义是当且仅当$\forall k\in[j,m]\quad A_{i+k-j}>=B_k$ ，根据这个定义就可以退出一个状态转移
$I_m$表示m位为1的bitset，这是为了保证只要$A_i>=B_i 那么cur[m]=1$,因为右移位的时候把cur[m]置为0了。
当cur[1]=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
36
37
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 150010;
const int M = 4e4+10;
const int INF = 1e9+7;
bitset<M>s[M];
bitset<M>cur;
pair<int,int> a[N],b[M];
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].first);
a[i].second=i;
}
for(int i=1;i<=m;i++){
scanf("%d",&b[i].first);
b[i].second=i;
}
sort(b+1,b+1+m);
b[m+1].first=INF;
b[m+1].second=m+1;
for(int i=1;i<=m;i++){
s[i]=s[i-1];
s[i].set(b[i].second);
}
bitset<M>I;
I.set(m);
int ans = 0;
for(int i=n;i>=1;--i){
int pos = upper_bound(b+1,b+1+m,a[i])-b-1;
cur = (cur>>1|I)&s[pos];
if(cur[1]==1)ans++;
}
printf("%d\n",ans);
}
|