Codeforces Round #566 (Div. 2)

由 Edwiv 发布于  ｜  50,561次浏览

自闭场，当场心态爆炸，c题小模拟不想写，E题是没学过的矩阵快速幂和欧拉降幂，减了50多分QAAAAAQ

A. Filling Shapes

time limit per test1 second memory limit per test256 megabytes

You have a given integer ?n. Find the number of ways to fill all 3×n tiles with the shape described in the picture below. Upon filling, no empty spaces are allowed. Shapes cannot overlap.

This picture describes when n=4. The left one is the shape and the right one is 3×?3×n tiles.Input

The only line contains one integer n (1≤?≤601≤n≤60) — the length.Output

Print the number of ways to fill.
Examplesinput

4

output

4

input

1

output

0

Note

In the first example, there are 44 possible cases of filling.

In the second example, you cannot fill the shapes in 3×1 tiles.

签到题

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int n;
int main(){
	cin>>n;
	if(n%2) puts("0");
	else printf("%dn",(int)pow(2,n/2));
}

B. Plus from Picture

time limit per test1 second memory limit per test256 megabytes

You have a given picture with size ?×ℎw×h. Determine if the given picture has a single "+" shape or not. A "+" shape is described below:

  • A "+" shape has one center nonempty cell.
  • There should be some (at least one) consecutive non-empty cells in each direction (left, right, up, down) from the center. In other words, there should be a ray in each direction.
  • All other cells are empty.

Find out if the given picture has single "+" shape.Input

The first line contains two integers ℎh and ?w (1≤ℎ1≤h, ?≤500w≤500) — the height and width of the picture.

The ?i-th of the next ℎh lines contains string ??si of length ?w consisting "." and "*" where "." denotes the empty space and "*" denotes the non-empty space.Output

If the given picture satisfies all conditions, print "YES". Otherwise, print "NO".

You can output each letter in any case (upper or lower).
Examplesinput

5 6
......
..*...
.****.
..*...
..*...

output

YES

input

3 5
..*..
****.
.*...

output

NO

input

7 7
.......
...*...
..****.
...*...
...*...
.......
.*.....

output

NO

input

5 6
..**..
..**..
******
..**..
..**..

output

NO

input

3 7
.*...*.
***.***
.*...*.

output

NO

input

5 10
..........
..*.......
.*.******.
..*.......
..........

output

NO

Note

In the first example, the given picture contains one "+".

In the second example, two vertical branches are located in a different column.

In the third example, there is a dot outside of the shape.

In the fourth example, the width of the two vertical branches is 22.

In the fifth example, there are two shapes.

In the sixth example, there is an empty space inside of the shape.

某场div3的E题的简化版本，用四个数组记一下每个点上下左右连续的"*"有几个，并且记一下一共有几个星号，然后再扫一遍，遍历每个点，如果它的上下左右都有星就是一个十字，再判断十字的星星总数和种的星星数相不相等

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)550;
int n,m,pre[maxn][maxn],suf[maxn][maxn],up[maxn][maxn],down[maxn][maxn];
char mp[maxn][maxn];
int tot=0;
int main(){
	cin>>n>>m;
	rep(i,1,n) scanf("%s",mp[i]+1);
	rep(i,1,n) rep(j,1,m) if(mp[i][j]=='*'){
		tot++;
		pre[i][j]=pre[i][j-1]+1;
		up[i][j]=up[i-1][j]+1;
	}
	dep(i,n,1) dep(j,m,1) if(mp[i][j]=='*'){
		suf[i][j]=suf[i][j+1]+1;
		down[i][j]=down[i+1][j]+1;
	}
	int ans=0;
	rep(i,1,n) rep(j,1,m) if(mp[i][j]=='*'){
		if(pre[i][j]>1&&suf[i][j]>1&&up[i][j]>1&&down[i][j]>1){
			ans++;
			if(pre[i][j]+suf[i][j]+up[i][j]+down[i][j]-3!=tot)
				return puts("NO"),0;
		}
	}
	if(ans!=1) return puts("NO"),0;
	return puts("YES"),0;
}

C. Beautiful Lyrics

time limit per test1 second memory limit per test256 megabytes

You are given ?n words, each of which consists of lowercase alphabet letters. Each word contains at least one vowel. You are going to choose some of the given words and make as many beautiful lyrics as possible.

Each lyric consists of two lines. Each line consists of two words separated by whitespace.

A lyric is beautiful if and only if it satisfies all conditions below.

  • The number of vowels in the first word of the first line is the same as the number of vowels in the first word of the second line.
  • The number of vowels in the second word of the first line is the same as the number of vowels in the second word of the second line.
  • The last vowel of the first line is the same as the last vowel of the second line. Note that there may be consonants after the vowel.

Also, letters "a", "e", "o", "i", and "u" are vowels. Note that "y" is never vowel.

For example of a beautiful lyric,"hello hellooowww"

"whatsup yowowowow"is a beautiful lyric because there are two vowels each in "hello" and "whatsup", four vowels each in "hellooowww" and "yowowowow" (keep in mind that "y" is not a vowel), and the last vowel of each line is "o".

For example of a not beautiful lyric,"hey man"

"iam mcdic"is not a beautiful lyric because "hey" and "iam" don't have same number of vowels and the last vowels of two lines are different ("a" in the first and "i" in the second).

How many beautiful lyrics can you write from given words? Note that you cannot use a word more times than it is given to you. For example, if a word is given three times, you can use it at most three times.Input

The first line contains single integer n (1≤n≤105) — the number of words.

The ?i-th of the next ?n lines contains string ??si consisting lowercase alphabet letters — the ?i-th word. It is guaranteed that the sum of the total word length is equal or less than 106106. Each word contains at least one vowel.Output

In the first line, print ?m — the number of maximum possible beautiful lyrics.

In next 2?2m lines, print ?m beautiful lyrics (two lines per lyric).

If there are multiple answers, print any.
Examplesinput

14
wow
this
is
the
first
mcdics
codeforces
round
hooray
i
am
proud
about
that

output

3
about proud
hooray round
wow first
this is
i that
mcdics am

input

7
arsijo
suggested
the
idea
for
this
problem

output

0

input

4
same
same
same
differ

output

1
same differ
same same

Note

In the first example, those beautiful lyrics are one of the possible answers. Let's look at the first lyric on the sample output of the first example. "about proud hooray round" forms a beautiful lyric because "about" and "hooray" have same number of vowels, "proud" and "round" have same number of vowels, and both lines have same last vowel. On the other hand, you cannot form any beautiful lyric with the word "codeforces".

In the second example, you cannot form any beautiful lyric from given words.

In the third example, you can use the word "same" up to three times.

中等规模的模拟，首先用结构体存每个单词，存下元音数量和最后一个元音，再对结构体排序，第一维降序第二维升序，然后再扫一遍，如果遇到i和i+1的元音数量相等并且最后一个相等那就放到一个vector里并且标记一下；
再双指针扫一遍，把元音数量相等但是最后一个不想等的放到一个vector里，那么答案就是第一个vector和第二个配对，如果第一个还有多的就再两两配对

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define F first
#define S second
typedef long long ll;
const int maxn=(int)1e5+100;
int n,vis[maxn];
struct node{
	string word;
	int num_vowel,last;
	friend bool operator<(const node &a,const node &b){
		return a.num_vowel==b.num_vowel?a.last<b.last:a.num_vowel>b.num_vowel;
	}
}s[maxn];
map<char,int> ck;
vector<pair<string,string> > la,fr;
int check(char c){
	if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')
		return ck[c];
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	ck['a']=1;ck['e']=2;ck['i']=3;ck['o']=4;ck['u']=5;
	cin>>n;
	rep(i,1,n){
		cin>>s[i].word;
		int tem=0;
		rep(j,0,s[i].word.length()-1) 
			if(tem=check(s[i].word[j]))
				s[i].num_vowel++,s[i].last=tem;
	} sort(s+1,s+1+n);
	rep(i,1,n){
		if(i+1<=n&&s[i].num_vowel==s[i+1].num_vowel&&s[i].last==s[i+1].last){
			la.pb({s[i].word,s[i+1].word});
			vis[i]=vis[i+1]=1;
			i++;
		}
	}
	int pre=0;
	rep(i,1,n){
		if(!vis[i]){
			if(!pre) pre=i;
			else if(s[pre].num_vowel==s[i].num_vowel){
				fr.pb({s[pre].word,s[i].word});
				pre=0;
			}
			else pre=i;
		}
	}
	int ans=min(fr.size(),la.size());
	if(la.size()-ans>0) ans+=(la.size()-ans)/2;
	cout<<ans<<"n";
	int pos1=0,pos2=0;
	rep(i,1,ans){
		if(pos1<fr.size()){
			cout<<fr[pos1].F<<" "<<la[pos2].F<<"n";
			cout<<fr[pos1++].S<<" "<<la[pos2++].S<<"n";
		}
		else{
			cout<<la[pos2].F<<" "<<la[pos2+1].F<<"n";
			cout<<la[pos2].S<<" "<<la[pos2+1].S<<"n";
			pos2+=2;
		}
	}
}

D. Complete Mirror

time limit per test1 second memory limit per test256 megabytes

You have given tree consist of ?n vertices. Select a vertex as root vertex that satisfies the condition below.

  • For all vertices (v_1) and (v_2), if distance(root,(v_1)) =distance(root, (v_2)) then ??????degree(?1v1) =??????=degree(?2v2), where ??????degree means the number of vertices connected to that vertex, and ????????distance means the number of edges between two vertices.

Determine and find if there is such root vertex in the tree. If there are multiple answers, find any of them.

Input

The first line contains a single integer n ((1leq ?leq 10^5)) — the number of vertices.

Each of the next n−1 lines contains two integers (v_i) and (u_i) ((1leq ?_? <?_?leq n)) — it means there is an edge exist between (v_i) and (u_i). It is guaranteed that the graph forms tree.Output

If there is such root vertex exists, print any of them. Otherwise, print −1−1.
Examplesinput

7
1 2
2 3
3 4
4 5
3 6
6 7

output

3

input

6
1 3
2 3
3 4
4 5
4 6

output

-1

Note

This is the picture for the first example. 11, 55, 77 also can be a valid answer.

This is the picture for the second example. You can see that it's impossible to find such root vertex.

首先，这个根节点到每个叶子节点的距离一定相等,那么我们找到树的直径，并判断直径两端的两个叶子节点是否可行，可行则输出。

若两个端点不可行，那么下一个可行的点一定只有直径端点的中点（直径长为偶数则无解），那么我们再判断一下中点可不可行，可行则输出。

第四种情况就是离直径中心最近的直接相连的叶子节点（就好像在中心点上连了一条链，check一下这条链的端点）

那么我们最多只需要check四个点就可以知道答案。
复杂度O(n)；

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
int n,head[maxn],cnt=1,de[maxn];
int st,ed,mid,dis[maxn],pre[maxn];
vector<int> p[maxn];
struct node{
	int v,next;
}g[maxn<<1];
void add(int u,int v){
	g[cnt]={v,head[u]}; head[u]=cnt++;
}
void dfs(int u){
	for(int i=head[u];i;i=g[i].next){
		int v=g[i].v;
		if(v==pre[u]) continue;
		dis[v]=dis[u]+1; pre[v]=u;
		dfs(v);
	}
}
int bfs(int u){
	queue<int> q; q.push(u);pre[u]=u;
	while(!q.empty()){
		u=q.front();q.pop();
		if(de[u]==1) return u;
		for(int i=head[u];i;i=g[i].next){
			int v=g[i].v;
			if(v==pre[u]||de[v]>2) continue;
			pre[v]=u; q.push(v);
		}
	}
	return -1;
}
bool check(int u){
	dis[u]=0;pre[u]=u;dfs(u);
	int maxx=0;
	rep(i,0,n) p[i].clear();
	rep(i,1,n){
		p[dis[i]].pb(i);
		maxx=max(maxx,dis[i]);
	}
	rep(i,0,maxx) for(auto v:p[i]){
		if(de[v]!=de[p[i][0]]){
			return 0;
		}
	}
	return 1;
}
void find_diame(){
	st=ed=1;
	dis[1]=0;pre[1]=1;dfs(1);
	rep(i,1,n) if(dis[st]<dis[i]) st=i;
	dis[st]=0;pre[st]=st;dfs(st);
	rep(i,1,n) if(dis[ed]<dis[i]) ed=i;
	if(dis[ed]%2) mid=-1; //直径长是偶数
	else{
		mid=ed;
		rep(i,1,dis[ed]>>1) mid=pre[mid];
	}
}
int main(){
	cin>>n;
	rep(i,1,n-1){
		int u,v; scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
		de[u]++;de[v]++;
	}
	find_diame();
	if(check(st)) return printf("%dn",st),0;
	if(check(ed)) return printf("%dn",ed),0;
	if(mid==-1) return puts("-1"),0;
	if(check(mid)) return printf("%dn",mid),0;
	mid=bfs(mid);
	if(mid==-1) return puts("-1"),0;
	if(check(mid)) return printf("%dn",mid),0;
	return puts("-1"),0;
}

E. Product Oriented Recurrence

time limit per test1 second memory limit per test256 megabytes

Let \(f_{x} = c^{2x-6} \cdot f_{x-1} \cdot f_{x-2} \cdot f_{x-3}\) for \(x \ge 4\).

You have given integers \(n, f_{1}, f_{2}, f_{3}\), and \(c\). Find \(f_{n} \bmod (10^{9}+7)\).

Input

The only line contains five integers \(n, f_{1}, f_{2}, f_{3}\), and \(c (4 \le n \le 10^{18}, 1 \le f_{1}, f_{2}, f_{3}, c \le 10^{9})\).

Output

Print \(f_{n} \bmod (10^{9} + 7)\).

Examplesinput

5 1 2 5 3

output

72900

input

17 97 41 37 11

output

317451037

Note

In the first example,\( f_{4} = 90, f_{5} = 72900\).

In the second example, \(f_{17} \approx 2.28 \times 10^{29587}\).

$$f_n=C^{2n-6}\cdot f_{n-1}\cdot f_{n-2}\cdot f_{n-3}\\
C^n f_n=C^{3n-6}\cdot f_{n-1}\cdot f_{n-2}\cdot f_{n-3}=C^{n-1}f_{n-1}\cdot C^{n-2}f_{n-2}\cdot C^{n-3}f_{n-3}$$

我们令\(g_n=C^nf_n\)，则：
$$g_n=g_{n-1}\cdot g_{n-2}\cdot g_{n-3}=g_1^{x_n}g_2^{y_n}g_3^{z_n}$$

以\(g_1\)为例：
$$g_1^{x_n}=g_1^{x_{n-1}}\cdot g_1^{x_{n-2}}\cdot g_1^{x_{n-3}} \Rightarrow x_n=x_{n-1}+x_{n-2}+x_{n-3}$$

同理，
$$\begin{cases}
y_n=y_{n-1}+y_{n-2}+y_{n-3}\\
z_n=z_{n-1}+z_{n-2}+z_{n-3}
\end{cases}$$

又有
$$\begin{cases}
x_1=1,y_1=0,z_1=0\\
x_2=0,y_2=1,z_2=1\\
x_3=0,y_3=0,z_3=1
\end{cases}$$

于是通过矩阵快速幂可以求得\(x_n，y_n，z_n\)，然后代到式子里就可以求得\(f_n\)了；注意在矩阵快速幂时取模要用欧拉降幂，也就是模\(1e9+6\)；

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
typedef long long ll;
const int maxn=(int)2e5+100;
const ll mod=(ll)1e9+7;
ll n,f1,f2,f3,c;
ll qpow(ll base,ll k){
	ll res=1;
	while(k){
		if(k&1) res=res*base%mod;
		base=base*base%mod;
		k>>=1;
	}
	return res%mod;
}
ll inv(ll b){return qpow(b,mod-2)%mod;}
struct mtix{
    ll a[5][5];
    mtix(){memset(a,0,sizeof(a));}
}f;
mtix mul(mtix a,mtix b){
    mtix c;
    rep(i,1,3) rep(j,1,3) rep(k,1,3){
        c.a[i][j]=c.a[i][j]+(a.a[i][k]*b.a[k][j])%(mod-1);
        c.a[i][j]%=(mod-1);//欧拉降幂
    }
    return c;
}
ll mpow(ll y,int op){
    mtix ans;
    mtix tem=f;
    rep(i,1,3) ans.a[i][i]=1;
    for (;y;tem=mul(tem,tem),y>>=1) if (y&1) ans=mul(ans,tem);
    return ans.a[1][op]%(mod-1);
}
int main() {
    cin>>n>>f1>>f2>>f3>>c;
    ll g1=c*f1%mod,g2=c*c%mod*f2%mod,g3=c*c%mod*c%mod*f3%mod;
    f.a[1][1]=1;f.a[1][2]=1;f.a[1][3]=1;f.a[2][1]=1;f.a[3][2]=1;
    ll xn=mpow(n-3,3),yn=mpow(n-3,2),zn=mpow(n-3,1);
    ll gn=qpow(g1,xn)*qpow(g2,yn)%mod*qpow(g3,zn)%mod;
    ll fn=gn*inv(qpow(c,n))%mod;
    printf("%lldn",fn);
}

订阅评论
提醒
0 评论
内联反馈
查看所有评论