A.串
题解：
dp
三维dp可能更好理解一些。 代表长度为
的字符串，当j=1时代表已经含有u了的字符串的个数，k=1时代表已经含有us的字符串的个数。
最后输出即可。
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=500+10;
const int mod=1e9+7;
int ans;
int pre[1000000+2][3][3];
///////////////////////////询问++++++
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
int n;
cin>>n;
pre[0][0][0]=1;
for(int i=1;i<=n;i++){
pre[i][0][0]=(pre[i-1][0][0]*25)%mod;
pre[i][1][0]=(pre[i-1][0][0]+pre[i-1][1][0]*25)%mod;
pre[i][1][1]=(pre[i-1][1][0]+pre[i-1][1][1]*26)%mod;
ans=(ans+pre[i][1][1])%mod;
}
cout<<ans<<endl;
return 0;
}
B. 括号
题解：
构造题
我们发现最长的括号序列长度为100000，那么我们看看这么长的括号序列最多能构造出多少个合法序列。
那种序列显而易见((((.......))))，左边5e4个括号，右边5e4个括号即可构造出2.5e9的合法括号，所以肯定是可以构造出来的，那么应该怎么构造呢。
1.当要求构造出来的合法括号个数小于99999个时，我们可以选择左边只有一个左括号，右边括号全是右括号构造即可，即()))))))...))))))
2.当大于时，我们考虑左括号直接放5e4个，然后开始添加右括号，每添加一个右括号，即意味着增加了5e4个合法括号。然后k=k-5e4，若k小于5e4，那么我们从左端开始数到第k个左括号，在他的右边添加一个右括号即可。
代码：
/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
const int maxn=110;
int pos=-1;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int k;
cin>>k;
if(k<=60000){
cout<<"(";
for(int i=0;i<k;i++) cout<<")";
}
else{
int ansr=0;
for(int i=0;i<50000;i++){
if(k<50000) break;
k-=50000;
ansr++;
}
for(int i=49999;i>=1;i--){
if(k==i){
pos=i;
break;
}
}
for(int i=1;i<=50000;i++){
cout<<"(";
if(i==pos){
cout<<")";
}
}
for(int i=0;i<ansr;i++) cout<<")";
}
}
C.红和蓝
题解：
贪心+染***r> 每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点。
通过这句话我们可以发现一个规律，每个点要跟一个颜色相同的点配对，且只能跟一个点配对。
所以我们要把所有的点两两配对，然后再把每对看成一个大点进行黑白染色即可。
那么我们如何对这棵树进行配对呢？
从树根开始？
好像不行，因为你不知道这个根节点具体要跟他的哪个孩子进行配对。
这题我们要实现完全配对，所以我们每个点都不可以落单，那么好办，我们从叶子节点往上进行组合即可。
如果发现有组合不起来的，那么直接输出-1即可
两边dfs，第一遍dfs进行两两配对，把一对的颜色染为相同的颜色，第二遍dfs进行黑白染色，把一对组合看成一个点。
代码：
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;
vector<int> edge[maxn];
int sz[maxn];
int col[maxn];
int cnt=0;
void dfs(int x,int fa){
sz[x]=1;
for(auto i:edge[x]){
if(i==fa) continue;
dfs(i,x);
sz[x]+=sz[i];
}
if(sz[x]==2){
++cnt;
sz[x]=0;col[x]=cnt;
for(auto i:edge[x]){
if(i==fa||col[i]) continue;
col[i]=cnt;
}
sz[x]=0;
}
}
int ansc[maxn];
void paint(int x,int fa){
for(auto i:edge[x]){
if(i==fa) continue;
if(col[i]==col[x]){
ansc[i]=ansc[x];
paint(i,x);
}
else{
if(ansc[x]==1) ansc[i]=2;
else ansc[i]=1;
paint(i,x);
}
}
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
int n;
cin>>n;
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(1,1);
if(sz[1]!=0||n&1){
cout<<-1<<endl;
return 0;
}
ansc[1]=1;
paint(1,1);
for(int i=1;i<=n;i++){
if(ansc[i]==1) cout<<"R";
else cout<<"B";
}
}
D. 点一成零
题解：
并查集+逆元
初始图所有的情况为 每个连通块大小相乘再乘连通块个数的阶乘
用一个pre进行维护每个连通块大小相乘，如果连通块的个数减小了我们用逆元动态的把减少的那个个数给除掉，然后再乘以新增加的大小。预处理n！的大小即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+1;
const int mod = 1e9+7;
char s[501][501];
long long p[maxn], tot;
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
int n, vis[501][501], f[maxn];
void dfs(int x, int y, int id) {
p[id] ++;
vis[x][y] = id;
for(int i = 0; i < 4; ++ i) {
int X = x + dir[i][0];
int Y = y + dir[i][1];
if (X <= n && X >= 1 && Y <= n && Y >= 1 && s[X-1][Y-1] == '1' && !vis[X][Y]) {
dfs(X, Y, id);
}
}
}
int fin(int x) {
if (x == f[x]) return x;
return f[x] = fin(f[x]);
}
long long inv[maxn], fac[maxn];
void get_inv(int n, int p) {
inv[1] = fac[0] = fac[1] = 1;
for(int i = 2; i <= n; ++ i) {
inv[i] = (p - p/i) * inv[p%i] % p;
fac[i] = fac[i-1] * i % p;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 0; i < n; ++ i) {
cin >> s[i];
}
get_inv(n*n, mod);
long long pre = 1;
for(int i = 1; i <= n; ++ i) {
for(int j = 1; j <= n; ++ j) {
if (s[i-1][j-1] == '1' && vis[i][j] == 0) {
dfs(i, j, ++ tot);
f[tot] = tot;
pre = pre * p[tot] % mod;
}
}
}
int T, m = tot;
cin >> T;
while(T --) {
int x, y;
cin >> x >> y;
if (s[x][y] == '1') cout << pre * fac[m] % mod << "\n";
else {
s[x][y] = '1';
vis[x+1][y+1] = ++tot;
f[tot] = tot;
m ++;
p[tot] = 1;
for(int i = 0; i < 4; ++ i) {
int X = x + dir[i][0];
int Y = y + dir[i][1];
if (X >= 0 && X < n && Y >= 0 && Y < n && vis[X+1][Y+1]) {
int re = fin(vis[X+1][Y+1]);
if (re == tot) continue;
f[re] = tot;
pre = pre * inv[p[re]] % mod;
p[tot] += p[re];
p[re] = 0;
m --;
}
}
pre = pre * p[tot] % mod;
cout << pre * fac[m] % mod << "\n";
}
}
return 0;
}
F.对答案一时爽
题解：
签到题
答案相同的话，假设都对，答案不同的话假设只有一个人答案正确。
题解：
/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
const int maxn=110;
char a[maxn];
char b[maxn];
signed main() {
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
}
int ans=0;
for(int i=0;i<n;i++){
if(a[i]==b[i]) ans+=2;
else ans++;
}
cout<<ans<<" "<<0<<endl;
}
I.限制不互素对的排列
题解：
构造体
对于小于等于5的长度，我们进行特判。
对于大于等于6的长度，一定可以构造出符合题意得序列。
如何构造呢，我们就把所有偶数放在最前面，结尾得数为6，后面紧跟一个3，这样得话我们就可以构造出最长长度得序列了。
代码：
/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e5+10+10;
bool visited[maxn];
///////////////////////////询问++++++
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin>>n>>k;
memset(visited,false,sizeof visited);
if(k==0){
for(int i=1;i<=n;i++) cout<<i<<" ";
}
else if(n<=3){
cout<<-1<<endl;
}
else if(n<=5){
if(n/2==k) cout<<-1<<endl;
else{
cout<<"2 ";
visited[2]=true;
for(int i=4;i<=n;i+=2){
cout<<i<<" ";
visited[i]=true;
k--;
if(k==0) break;
}
for(int i=1;i<=n;i++){
if(!visited[i]) cout<<i<<" ";
}
}
}
else{
if(n/2==k){
for(int i=2;i<=n;i+=2){
if(i==6) continue;
cout<<i<<" ";
visited[i]=true;
}
visited[6]=visited[3]=1;
cout<<"6 3 ";
for(int i=1;i<=n;i++){
if(!visited[i])
cout<<i<<" ";
}
}
else{
cout<<"2 ";
visited[2]=true;
for(int i=4;i<=n;i+=2){
cout<<i<<" ";
visited[i]=true;
k--;
if(k==0) break;
}
for(int i=1;i<=n;i++){
if(!visited[i]) cout<<i<<" ";
}
}
}
}
J.一群小青蛙呱蹦呱蹦呱
题解：
对每个素数对最终答案的贡献分别计算。
图片来源于：https://blog.nowcoder.net/n/b1889cff065d48469c63dee1942a2862
然后我们用欧拉筛提前预处理出所有小于n/2得素数即可
代码：
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int maxn = 1.6e8+1;
const int mod = 1e9+7;
using namespace std;
int prime[maxn],tot;
bool visit[maxn];
bool vis[maxn];
void Prime(int n){
vis[1]=1;
for (int i = 2;i <= n; i++) {
//cout<<" i = "<<i<<endl;
if (!visit[i]) {
prime[++tot] = i; //纪录素数， 这个prime[0] 相当于 cnt，用来计数
}
for (int j = 1; i*prime[j] <= n; j++) {
// cout<<" j = "<<j<<" prime["<<j<<"]"<<" = "<<prime[j]<<" i*prime[j] = "<<i*prime[j]<<endl;
visit[i*prime[j]] = 1;
if (i % prime[j] == 0) {
break;
}
}
}
}
int sol(int n,int m) {
int res=1;
while(n>=m) {
res=res*m%mod;
n/=m;
}
return res;
}
///////////////////////////询问++++++
signed main() {
int n;
cin>>n;
if(n<6){
cout << "empty";
return 0;
}
Prime(n);
long long lcm = sol(n/3, 2);
for(int i=2;i<=tot;++i) {
lcm=lcm*sol(n/2,prime[i]) % mod;
}
cout <<lcm<< "\n";
return 0;
}
京公网安备 11010502036488号