MZOI20200516题解
starseven
2020-05-16 11:45:06
## 下面是我在考场上写的题解
### T1
这明显是一道“查重”的题，也就是在这个字符串中不能有两个相同的ans+i的字符串。
#### 我们先作以下规定
>>> 字符串为txt，长度为len
看到这里，我们心里要有些瞎（~~遐~~）想，怎么记录这个呢？
最开始想到了二分，但是发现不可做，因为两个相同的字符串可能出现在任何地方,如果这样二分答案的话，虽然答案具有单调性，可是需要枚举l-mid种可能性，所以我们不用。
（~~我不会告诉你我不用的原因是因为我不会二分~~）
然后我就想到了kmp匹配，如果我从开始匹配起，每一次不仅记录next数组，我还新增加一个lon数组以用来记录长度，这样的话就可以知道重复的长度有多少，所以我一开始的代码就出来了
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#define ri register int
#define Starseven main
using namespace std;
const int N=120;
char txt[N];
int ioi[N];
int lon[N];
void Pre_Next(){
int s1=0,s2;
ioi[0]=s2=-1;
int ans=0;
int len2=strlen(txt),len=0;
while(s1<len2){
if(s2==-1||txt[s1]==txt[s2]){
if(s2==-1) len=0;
else len++;
ioi[++s1]=++s2;
lon[s1]=len;
ans=max(ans,len);
}
else{
ans=max(ans,len);
s2=ioi[s2];
len=lon[s2];
}
}
cout<<ans<<endl;
return ;
}
int Starseven(void){
cin>>txt;
Pre_Next();
return 0;
}
```
样例毫无疑问地过了，然后我手造了一组数据
$$ fghgwooh $$
我的输出是0，结果应该是1，我就开始思考了，为什么呢？？
我又想到了一点，然后输出了next数组，对了！next数组只是从开始匹配，如果中间有什么东西的话就不得行了，所以我们应该枚举起点，然后做len次kmp匹配。
所以我改了一下：
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#define ri register int
#define Starseven main
using namespace std;
const int N=120;
char txt[N],a[N];
int ioi[N];
int lon[N];
int ans=0;
void Pre_Next(int len2){
int s1=0,s2;
memset(ioi,0,sizeof(ioi));
memset(lon,0,sizeof(lon));
ioi[0]=s2=-1;
int len=0;
while(s1<len2){
if(s2==-1||txt[s1]==txt[s2]){
if(s2==-1) len=0;
else len++;
ioi[++s1]=++s2;
lon[s1]=len;
ans=max(ans,len);
}
else{
ans=max(ans,len);
s2=ioi[s2];
len=lon[s2];
}
}
return ;
}
int Starseven(void){
cin>>a;
int l=strlen(a);
for(ri i=0;i<l;i++){
for(ri j=i;j<l;j++) txt[j-i]=a[j];
Pre_Next(l-i);
}
cout<<ans<<endl;
return 0;
}
```
然后就没管了。
### T2
T2不想多讲，我在考场上一看便是最小生成树，粘代码:
(~~别急，最小生成树可不可以用于最大~~)
这是个问题。
额，关键是，如果我们将权值取反然后求最小生成树，不就变成了最大生成树了吗？？
（当然，这是我考场的想法）
代码：
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ri register int
#define Starseven main
using namespace std;
const int N=200000+20;
int read();
void write(int);//要记得自己加换行和空格
int n,m,all,ans,fa[N>>1];
struct node{
int from,to,va;
}dis[N<<1];
bool cmp(const node &a,const node &b){
return a.va<b.va;
}
int Find(int x){
if(fa[x]==x) return x;
else return fa[x]=Find(fa[x]);
}
void Merge(int fx,int fy){
fa[fx]=fy;return ;
}
int Starseven(void){
n=read(),m=read();
for(ri i=1;i<=m;i++){
dis[i].from=read();
dis[i].to=read();
dis[i].va=read();
all+=dis[i].va;
dis[i].va=-dis[i].va;
}
for(ri i=1;i<=n;i++) fa[i]=i;
sort(dis+1,dis+1+m,cmp);
int ti=0;
for(ri i=1;i<=m;i++){
int x=dis[i].from,y=dis[i].to;
int fx=Find(x),fy=Find(y);
if(fx==fy) continue;
Merge(fx,fy);
ans+=dis[i].va;
ti++;
if(ti==n-1) break;
}
write(all+ans);
return 0;
}
int read(){
char ch=getchar();
int re=0,op=1;
while(ch<'0'||ch>'9'){
if(ch=='-') op=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
re=(re<<3)+(re<<1)+ch-'0';
ch=getchar();
}
return re*op;
}
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
```
### T3
现在我们来到了T3。
我一看编=便知道是容斥原理，主要是枚举子集这里，幸好我在牛客网网课上看了的
```
for(ri x=sc;x;x=(x-1)&sc)
```
其他的不多说，然后就是long long的问题
```cpp
#include<cstdio>
#include<iostream>
#define ri register int
#define Starseven main
#define ll long long
using namespace std;
int read();
void write(ll);//要记得自己加换行和空格
int n;
ll have[1<<11];
ll ans=0;
ll Judge(int x){
int num=0;
while(x){
if(x&1) num++;
x>>=1;
}
if(num%2!=0) return 1;
else return -1;
}
ll Power(ll x){
return (x-1)*x/2;
}
void init(){
freopen("3.in","r",stdin);
// freopen("3.out","w",stdout);
}
int Starseven(void){
//init();
n=read();
for(ri i=1;i<=n;i++){
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
int sc=0,re=0;
while(ch>='0'&&ch<='9'){
int gg=ch-'0';
re=1<<gg;
sc=sc|re;
ch=getchar();
}
for(ri x=sc;x;x=(x-1)&sc) have[x]++;
}
int all=(1<<10)-1;
for(ri x=all;x;x--){
if(have[x]<2) continue;
ans=ans+Power(have[x])*Judge(x);
}
write(ans);
return 0;
}
int read(){
char ch=getchar();
int re=0,op=1;
while(ch<'0'||ch>'9'){
if(ch=='-') op=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
re=(re<<3)+(re<<1)+ch-'0';
ch=getchar();
}
return re*op;
}
void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
```
关键来了，我闲得无聊，于是就写了个暴力程序对拍，小数据都对了，可是到了n=100000，时，我的程序输出和我的对拍程序输出不同
$$ What\;can\;I \;do\;? $$
于是我就没有管了。
-----------
以上的东西都是我在考场上写的东西，之后的东西得看我的成绩。（~~哈哈哈~~）
-------------------
下面是比赛后写的：
T1&T3得了分，T2爆炸
事实证明当你春风得意的时候，应该检查一下long long
我哭了,哈哈哈哈哈哈哈
现在附上T2正解
```cpp
#include<cstdio>
#include<iostream>
#define ri register int
#define Starseven main
#define ll long long
using namespace std;
int read();
void write(ll);//要记得自己加换行和空格
int n;
ll have[1<<11];
ll ans=0;
ll Judge(int x){
int num=0;
while(x){
if(x&1) num++;
x>>=1;
}
if(num%2!=0) return 1;
else return -1;
}
ll Power(ll x){
return (x-1)*x/2;
}
void init(){
freopen("3.in","r",stdin);
// freopen("3.out","w",stdout);
}
int Starseven(void){
//init();
n=read();
for(ri i=1;i<=n;i++){
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
int sc=0,re=0;
while(ch>='0'&&ch<='9'){
int gg=ch-'0';
re=1<<gg;
sc=sc|re;
ch=getchar();
}
for(ri x=sc;x;x=(x-1)&sc) have[x]++;
}
int all=(1<<10)-1;
for(ri x=all;x;x--){
if(have[x]<2) continue;
ans=ans+Power(have[x])*Judge(x);
}
write(ans);
return 0;
}
int read(){
char ch=getchar();
int re=0,op=1;
while(ch<'0'||ch>'9'){
if(ch=='-') op=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
re=(re<<3)+(re<<1)+ch-'0';
ch=getchar();
}
return re*op;
}
void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
```