Good Bye 2020

A.Bovine Dilemma
在X轴上给n个点,然后再给一个(0,1)点,求能组成多少面积不同的三角形所有三角形必定有(0,1)点,只有高不同,所以判断X轴上两两点之间的距离的数量即可

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int vis[105];
int a[105];
void work()
{
    int n;
    scanf("%d",&n);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
    	scanf("%d",&a[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
    	for(int j=i+1;j<=n;j++){
    		int x=a[j]-a[i];
    		if(!vis[x]){
    			vis[x]=1;
    			ans++;
    		}
    	}
    }
    printf("%d\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

B.Last minute enhancements
给定n个数,你可以给其中一些数加一,求最大不同数的数量
从大到小贪心的选择该数是否加一即可。

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[N];
int vis[N];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=2*n+1;i++){
    	vis[i]=0;
    }
    for(int i=1;i<=n;i++){
    	scanf("%d",&a[i]);
    	vis[a[i]]++;
    }
    for(int i=2*n;i>=1;i--){
    	if(vis[i]&&!vis[i+1]){
    		vis[i+1]++;
    		vis[i]--;
    	}
    }
    int ans=0;
    for(int i=1;i<=2*n+1;i++){
    	if(vis[i])ans++;
    }
    printf("%d\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C.Canine poetry
给定一个字符串,修改其中的一些字符,使得该串不存在长度大于等于2的回文串
因为不存在2的回文就不存在4的回文,不存在3的回文就不存在5的回文,只要将长度为2和3的回文串进行修改即可。在修改时考虑修改后面的那个字母,因为后面的字母可能还可以作为回文串的开头,但前面的字母就不会了。

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
char a[N];
void work()
{
    scanf("%s",a+1);
    int n=strlen(a+1);
    int ans=0;
    for(int i=2;i<=n;i++){
    	if(a[i]==a[i-1]||a[i]==a[i-2]){
    		ans++;
    		a[i]=0;
    	}
    }
    printf("%d\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

D.13th Labour of Heracles
给定一棵树,每个点有点权,对其边进行k染色,最终的答案为每种颜色的边所构成的最大连通块点权的和,求1到n-1染色的答案。
考虑极限染色情况,每个点可以被计入答案的次数为他的度数,所以直接按点大小排序,按照度数进行计算即可。

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
vector<int>v[N];
int in[N];
int a[N];
int id[N];
ll ans[N];
bool cmp(int x,int y)
{
	return a[x]>a[y];
}
void work()
{
    int n;
    scanf("%d",&n);
    ans[1]=0;
    for(int i=1;i<=n;i++){
    	scanf("%d",&a[i]);
    	v[i].clear();
    	in[i]=0;
    	id[i]=i;
    	ans[1]+=a[i];
    }
    for(int i=1;i<n;i++){
    	int x,y;
    	scanf("%d%d",&x,&y);
    	v[x].push_back(y);
    	v[y].push_back(x);
    	in[x]++;
    	in[y]++;
    }
    sort(id+1,id+n+1,cmp);
    int now=2;
    for(int i=1;i<=n;i++){
    	int x=id[i];
    	if(in[x]<=1)continue;
    	for(int j=now;j<min(now+in[x]-1,n);j++){
    		ans[j]=ans[j-1]+a[x];
    	}
    	// for(auto y:v[x]){
    	// 	in[y]--;
    	// }
    	now+=in[x]-1;
    }
    for(int i=1;i<n;i++){
    	printf("%lld ",ans[i]);
    }
    printf("\n");

}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

E.Apollo versus Pan
求\(\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n(a_i \& a_j)*(a_j|a_k)\)
考虑枚举j,然后得到的答案就是$\sum_{i=1}^n(a_i&a_j)*\sum_{k=1}^n(a_j|a_k)$,考虑分别求和,对于前一个式子,只要求出有多少二进制位满足($a_j$为1),然后总的计数即可。对于后面这个式子,对于$a_j$为1的位置全部计入,其他二进制位通过预处理统计即可,然后求和。将两个式子的乘积求和即为答案

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=5e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll a[65];
ll b[N];
void work()
{
    memset(a,0,sizeof(a));
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    	ll x;
    	scanf("%lld",&x);
    	b[i]=x;
    	int cnt=0;
    	while(x){
    		if(x&1)a[cnt]++;
    		cnt++;
    		x>>=1;
    	}
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
    	ll tmp=0;
    	ll tmp1=0;
    	ll x=b[i];
    	int cnt=0;
    	for(int j=0;j<60;j++){
    		if((1ll<<j)&x){
    			tmp=(tmp+a[j]*qpow(2,j)%p)%p;
    			tmp1=(tmp1+n*qpow(2,j)%p)%p;
    		}else{
    			tmp1=(tmp1+a[j]*qpow(2,j)%p)%p;
    		}
    	}
    	ans=(ans+tmp*tmp1%p)%p;
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

F.Euclid’s nightmare
n个向量m维,向量相加为每一维相加后对2取余,求最多有多少种向量可以通过这n个向量得到,并且求出最小的向量子集,并且要求字典序最小。每个向量中最多有2个位置为1
有1个位置为1的向量,其可以将该位置任意变化,有2个位置为1的向量,其可以将2个位置同时变化。考虑并查集,对于一个由2个位置为1的向量所连成的连通块来说,答案是1的数量为偶数的数量,就是$2^(size-1)$,可以发现不断增加连通块大小更优。如果存在只有1个位置为1 的向量,答案就是$2^size$。按这样贪心即可

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=5e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int fa[N];
int vis[N];
int siz[N];
int find(int x)
{
	if(fa[x]!=x)return fa[x]=find(fa[x]);
	return x;
}
void uni(int x,int y)
{
	x=find(x);
	y=find(y);
	if(vis[x]){
		fa[y]=x;
		siz[x]+=siz[y];
	}else{
		fa[x]=y;
		siz[y]+=siz[x];
	}
}
vector<int>v;
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    	fa[i]=i;
    	siz[i]=1;
    }
    for(int i=1;i<=n;i++){
    	int k;
    	scanf("%d",&k);
    	if(k==1){
    		int x;
    		scanf("%d",&x);
    		if(!vis[find(x)]){
    			vis[find(x)]=1;
    			v.push_back(i);
    		}
    	}else{
    		int x,y;
    		scanf("%d%d",&x,&y);
    		if(find(x)==find(y))continue;
    		if(vis[find(x)]&&vis[find(y)])continue;
    		uni(x,y);
    		v.push_back(i);
    	}
    }
    // ll ans=1;
    // for(int i=1;i<=m;i++){
    // 	if(fa[i]==i){
    // 		ans=ans*qpow(2,siz[i]-1+vis[i])%p;
    // 	}
    // }
    printf("%lld %d\n",qpow(2,v.size()),v.size());
    for(auto x:v){
    	printf("%d ",x);
    }
    printf("\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

G.Song of the Sirens
给定s0和t串,$s_i=s_{i-1}+t_i+s_{i-1}$,给定q个询问,每次询问第x个串中给定串出现的次数
考虑hash,可以发现,s串的头尾是相同的,所以当s串超过询问串的长度时,其往后继续增加所增加的贡献是可以计算出来的。首先对于s串中已经存在的部分,其往后的贡献都是乘2,然后考虑拼接部分的贡献,考虑求出所有字母在所有位置时是否可以拼出该子串,然后通过前缀和计数(注意拼成后,继续往下一个串走时要乘2,所以预处理时应该是不断乘二的预处理),即可获得答案。
t了一年,发现数组开小了,等fst完交一下看看。
update:确实 数组开小了  第一发就是对的

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
typedef unsigned long long ull;
const int N=2e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
string s,t;
ull pw[N];
ull pre[N];
ll pre1[100005][26];
ll ans[N];
struct node
{
	int x;
	string y;
	int id;
}a[N];
bool cmp(node x,node y)
{
	return x.y.length()<y.y.length();
}
void work()
{
    int n,q;
    cin>>n>>q;
    cin>>s>>t;
    for(int i=1;i<=q;i++){
    	cin>>a[i].x>>a[i].y;
    	a[i].id=i;
    }
    for(int i=1;i<=t.length();i++){
    	for(int j=0;j<26;j++){
    		pre1[i][j]=pre1[i-1][j]*2%p;
    	}
    	pre1[i][t[i-1]-'a']++;
    }
    sort(a+1,a+q+1,cmp);
    for(int i=1;i<=s.length();i++){
    	pre[i]=pre[i-1]*13131+s[i-1]-'a';
    }
    int now=0;
    for(int i=1;i<=q;i++){
    	while(a[i].y.length()>s.length()){
    		int len=s.length();
    		s+=t[now]+s;
    		now++;
    		for(int j=len+1;j<=s.length();j++){
    			pre[j]=pre[j-1]*13131+s[j-1]-'a';
    		}
    	}
    	if(now>a[i].x){
    		ans[a[i].id]=0;continue;
    	}
    	int len=a[i].y.length();
    	ull tmp=0;
    	for(int j=1;j<=len;j++){
    		tmp=tmp*13131+a[i].y[j-1]-'a';
    	}
    	ll sum=0;
    	for(int j=len;j<=s.length();j++){
    		if(tmp==pre[j]-pre[j-len]*pw[len]){
    			sum++;
    		}
    	}
    	int ss[26];
    	memset(ss,0,sizeof(ss));
    	for(int j=1;j<=len;j++){
    		for(int k=0;k<26;k++){
    			if((pre[s.length()]-pre[s.length()-j+1]*pw[j-1])*pw[len-j+1]+k*pw[len-j]+pre[len-j]==tmp){
    				//printf("%d %d\n",a[i].id,k);
    				ss[k]++;
    			}
    		}
    	}
    	ans[a[i].id]=sum*qpow(2,a[i].x-now);
    	for(int j=0;j<26;j++){
    		ans[a[i].id]+=ss[j]*(pre1[a[i].x][j]-pre1[now][j]*qpow(2,a[i].x-now)%p)%p;
    		ans[a[i].id]=(ans[a[i].id]%p+p)%p;
    	}
    }
    for(int i=1;i<=q;i++){
    	printf("%lld\n",ans[i]);
    }
}
int main()
{
	pw[0]=1;
	for(int i=1;i<N;i++){
		pw[i]=pw[i-1]*13131;
	}
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注