A 签到

B 二分图

C 找规律,计数

D 计算几何,三角形的五心(*)

A 签到

考虑全都是一个字母的情况,显然是$N/2$.不全都是一个字母,考虑单个字符串内的连续字符,每个连续字符都会贡献答案$|S|$,再考虑首尾相邻的情况,统计答案即可.

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
const int maxn=200;
ll K;
string s,p;
ll q(string s)
{
int len=s.length();
vector<ll> ans;
ans.clear();
int now=s[0];
int res=1;
for(int i=1;i<len;i++)
{
if(s[i]==now) res++;
else
{
now=s[i];
ans.push_back(res);
res=1;
}
}
ans.push_back(res);
ll sum=0;
for(auto p:ans)
{
sum+=(p/2);
}
return sum;
}
int main()
{
cin>>s;
read(K);
p=s+s;
bool ok=true;
for(int i=0;i<s.length();i++)
if(s[i]!=s[0]) ok=false;
if(ok)
{
cout<<(K*s.length())/2;
return 0;
}
ll sum1=q(s);
ll sum2=q(p);
ll pos=sum1*2-sum2;
cout<<sum1*K-pos*(K-1);
}

B 二分图.

显然二分图无解.

考虑不是二分图的情况,我们贪心的找出距离最远的两个点,把其中一个点放到$V_1$内,然后按照距离划分集合.

证明这个做法的正确性:因为不是二分图,因此这样做不可能存在两个相连的点到那个点的距离相等.同时考虑这3样做的最优性:因为如果有比当前做法更优的划分,那么最远距离就不能达到最远距离.

使用$floyd$算法,时间复杂度$O(n^3)$

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
#define all(x) x.begin(),x.end()
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
int N;
const int maxn=205;
int mp[maxn][maxn];
char pp[maxn][maxn];
ll dis[maxn][maxn];
int color[maxn];
bool dfs(int u,int c)
{
color[u]=c;
for(int j=0;j<N;j++)
if(mp[u][j]==1)
{
if(color[j]==c) return false;
else if(!color[j]&&!dfs(j,c==1?2:1)) return false;
}
return true;
}
int main()
{
read(N);
for(int i=0;i<N;i++)
scanf("%s",pp[i]);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
char c;
c=pp[i][j];
if(c=='1')
mp[i][j]=1;
else mp[i][j]=0;
}
if(!dfs(0,1))
{
cout<<"-1";
return 0;
}
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if(i==j) dis[i][j]=0;
else
{
dis[i][j]=(mp[i][j]==0)?2000000:1;
}
}
for(int k=0;k<N;k++)
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
ll ans=0;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if(dis[i][j]!=2000000){
{
ans=max(ans,dis[i][j]);
}}}
cout<<ans+1;

}

C 计数

考虑这种运算的本质:其实就是把后几位取反扔到前面去.那么显然$2N$次操作以后一定可以复原.

那么考虑循环的性质,最小的复原操作次数$k$一定是$2N$的因子.

我们可以枚举这个$k$,再用容斥原理统计答案.考虑现在$k$次操作可以复原,模拟这种运算的本质,我们发现:一定不能是整段$k$的循环(因为一个二进制不可能等于他的取反).

那么其实只有可能是$k$在中间断开循环.循环节其实是由互相取反的两段长度为$\frac{k}{2}$的二进制组成的.

然后我们只需要考虑这个$k/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
/*
* @Author: RBQRBQ
* @Date: 2020-04-09 23:57:16
* @LastEditors: RBQRBQ
* @LastEditTime: 2020-04-10 01:23:33
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
const int mod=998244353;
const int maxn=400000+10;
char num[maxn];
ll ans[maxn];
ll pow_2[maxn];
char tw[maxn];
int N;
int mystrcmp(char* c1,char* c2)
{
for(int i=1;i<=N;i++)
{
if(c1[i]>c2[i])
return 1;
if(c1[i]<c2[i])
return -1;
}
return 0;
}
int main()
{
read(N);
for(int i=1;i<=N;i++)
{
char s;
s=getchar();
num[i]=s;
}
pow_2[0]=1;
for(int i=1;i<maxn;i++)
pow_2[i]=pow_2[i-1]*2%mod;
for(int k=1;k<=N;k++)
{
if(N%k==0&&N/k%2==1)
{

ll res=0;
for(int i=k;i>=1;i--){
res=(res+(((num[i]-'0')==1)?pow_2[k-i]:0))%mod;
}
res++;
for(int i=1;i<=N;i+=2*k)
{
int ca=0;
for(int j=i;j<=i+k-1;j++)
tw[j]=num[++ca];
ca=0;
for(int j=i+k;j<=i+2*k-1;j++)
tw[j]=num[++ca]=='0'?'1':'0';
}
if(mystrcmp(tw,num)>0) {res=(res-1+mod)%mod;}
ans[k]=res%mod;
}
}
for(int i=1;i<=N;i++)
{
for(int j=2*i;j<=N;j+=i)
ans[j]=(ans[j]-ans[i]+mod)%mod;
}
ll sum=0;
for(int i=1;i<=N;i++)
if(N%i==0&&(N/i)%2==1)
sum=(sum+2*i*ans[i])%mod;
cout<<sum;
}

D 计算几何,三角形的五心

首先考单位圆上取三个点$A,B,C$如何计算内心$I$:

设在复平面上的单位圆$O$上有三个点$A,B,C$,分别记为$x^2,y^2,z^2(x,y,z\in \textbf{C},|x|=|y|=|z|=1)$;延长$AI,BI,CI$交圆$O$为$D,E,F$.那么$B,C$关于$OE$对称,设$D$为$d,d\in\textbf{C}$,复数计算法则可得:
$$
\frac{y^2}{d}=\overline{(\frac{z^2}{d})}=\frac{\overline{z^2}}{\overline{d}}
$$
$$
d=-yz(舍去正根)
$$

同理可得:$e=-xz,f=-xy$,因此$\Delta DEF$的垂心是$(d+e+f)$,同理可得$\Delta ABC$的内心的坐标是$(-yz-xz-xy)$,因此它们重合.

接下来只需要考虑每个线段对答案的贡献即可,这样就只需要枚举不同线段的个数就可以了,时间复杂度在$n^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
/*
* @Author: RBQRBQ
* @Date: 2020-04-12 22:42:18
* @LastEditors: RBQRBQ
* @LastEditTime: 2020-04-12 23:54:47
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
ll N;
long double L;
const int maxn=5000;
long double T[maxn];

#define pi 3.14159265358979323846
int main()
{
cin>>N>>L;
for(int i=1;i<=N;i++)
cin>>T[i];
long double rx=0.0,ry=0.0;
for(int i=1;i<=N;i++)
for(int j=i+1;j<=N;j++)
{
rx+=(N-2*j+2*i)*cos((long double)2*pi*(T[j]+T[i])/(long double )(2.0*L));
ry+=(N-2*j+2*i)*sin((long double)2*pi*(T[j]+T[i])/(long double)(2.0*L));
}
cout<<fixed<<setprecision(13)<<(long double)(6*rx)/(long double)((N)*(N-1)*(N-2))<<" "<<(long double)(6*ry)/(long double)((N)*(N-1)*(N-2));
}