首页 > 其他分享 >河南萌新联赛2024第（二）场 （CDEG）

河南萌新联赛2024第（二）场 （CDEG）

时间：2024-07-26 22:07:56浏览次数：11  
标签：const CDEG int res ll long 2024 萌新 define

C、小w和大W的决斗

博弈论
sg函数打表即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define endl '\n'
#define fi first
#define se second
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define lyh(i,a,b) for(int i=a;i<b;i++)
#define hyl(i,a,b) for(int i=a;i>b;i--)
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int ddx[8]={-1, 0, 1, 0, 1, -1, 1, -1};
const int ddy[8]={0, 1, 0, -1, -1, 1, 1, -1};
const int INF=0x3f3f3f3f;
const int N=2e5+10;
const int M=1010;
int n,m;
int mod,fa[N];
int Fpow(int b,int p){long long res=1;for(;p;p>>=1,b=b*b%mod)if(p&1)res=res*b%mod;return res;}
int qmi(ll a,ll k,ll p){ll res = 1;while (k) {if (k&1) res = res * a % p; k >>= 1;a = a * a % p;}return res;}
void init() {for(int i=1;i<=n;i++) fa[i]=i;}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void add(int a,int b) {int x=find(a);int y=find(b);fa[x]=y;}
bool ask(int a,int b) {return find(a)==find(b);}
int a[N];
vector<int>f(105,-1);

int sg(int x)
{
	if(f[x]!=-1) {
		return f[x];
	}
	set<int>st;
	
	for(int i=1;i<=x;i++)   //操作一
	{
		st.insert(sg(x-i));
	}
	
	for(int i = 1;i<x-2;i++)  //操作二
	{
		for(int j = 1;i+j<x;j++)
		{
			st.insert(sg(i)^sg(j)^sg(x-i-j));
		}
	}
	for(int i=0;;i++)
	{
		if(!st.count(i)) return f[x] = i; 
	}
}
void solve()
{
	cin>>n;
	int ans = 0;
	for (int i = 1;i <= n;i ++)
    {
    	int x;
        cin >> x;
        ans ^= sg(x);
    }
	if(ans>0){
		cout<<"w win"<<endl;
		return;
	}else{
		cout<<"W win"<<endl;
		return;
	}
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

D、A*BBBB

题解中说：模拟乘法发现，当B每一位相同时假设为x，那么就是A乘x，然后B有多少位就往前移多少次，然后再用前缀和进行维护当前位数为多少。
我们首先举一个例子：114514 与 22222 相乘

114514*2 = 229028

114514 与 22222 相乘
        1 1 4 5 1 4
    x     2 2 2 2 2
--------------------
        2 2 9 0 2 8
      2 2 9 0 2 8 
    2 2 9 0 2 8
  2 2 9 0 2 8
2 2 9 0 2 8
---------------------
     我们都知道，答案的总长度是|a|+|b|
     相乘结果的每一列都是一个区间
     用l和r表达这个区间，并用前缀和和差分计算即可
                 8
               2 8
             0 2 8
           9 0 2 8 
         2 9 0 2 8
       2 2 9 0 2
       2 2 9 0
       2 2 9
       2 2
       2

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define endl '\n'
#define fi first
#define se second
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define lyh(i,a,b) for(int i=a;i<b;i++)
#define hyl(i,a,b) for(int i=a;i>b;i--)
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int ddx[8]={-1, 0, 1, 0, 1, -1, 1, -1};
const int ddy[8]={0, 1, 0, -1, -1, 1, 1, -1};
const int INF=0x3f3f3f3f;
const int N=5e6+10;
const int M=1010;
int n,m;
int mod,fa[N];
int Fpow(int b,int p){long long res=1;for(;p;p>>=1,b=b*b%mod)if(p&1)res=res*b%mod;return res;}
int qmi(ll a,ll k,ll p){ll res = 1;while (k) {if (k&1) res = res * a % p; k >>= 1;a = a * a % p;}return res;}
void init() {for(int i=1;i<=n;i++) fa[i]=i;}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void add(int a,int b) {int x=find(a);int y=find(b);fa[x]=y;}
bool ask(int a,int b) {return find(a)==find(b);}
string a,b;
int pr[N];
void solve()
{
	cin>>a>>b;
	if(a[0]=='0'||b[0]=='0'){  
		cout<<0<<endl;
		return;
	}
	
	reverse(a.begin(),a.end());   //乘法是从个位开始向前计算的
	vector<int>v;
	int B = b[0]-'0';
	int t = 0;
    for (int i = 0; i < a.size(); i ++ )  //计算A与B【0】的乘积
    {
       	t += (a[i]-'0')*B;
        v.push_back(t % 10);
        t /= 10;
    }
    while(t)
    {
    	v.push_back(t % 10);
        t /= 10;
    }
    reverse(v.begin(),v.end());
    
    //求前缀和
    //这里从1开始记录，方便计算
    for(int i=1;i<=v.size();i++)  
    {
    	pr[i] = pr[i-1]+v[i-1];
    }
    
    int n = v.size();
    int m = b.size();
    int p = 0;
    vector<int>ans;
    
    for(int i =1;i<=n+m-1;i++)   //模拟A与BBB……相乘的加法
    {
    	int l =max(0ll,n-i);
    	int r = min(n,n+m-i);
    	p += pr[r]-pr[l];
    	ans.push_back(p%10);
    	p/=10;
    } 
    while(p){
    	ans.push_back(p%10);
    	p/=10;
    }
    reverse(ans.begin(),ans.end());
    
    for(int i=0;i<ans.size();i++) cout<<ans[i];
    cout<<endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

E、“好”字符

这题考察了字符串哈希
字符串哈希模板：

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}

操作1 ：将字符串复制并连接在结尾。
操作2 ：将字符串根据每个字符是否为字符 转化为一个01串（或将字符x以外的字符全部转化为特殊字符）
code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define endl '\n'
#define fi first
#define se second
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define lyh(i,a,b) for(int i=a;i<b;i++)
#define hyl(i,a,b) for(int i=a;i>b;i--)
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int ddx[8]={-1, 0, 1, 0, 1, -1, 1, -1};
const int ddy[8]={0, 1, 0, -1, -1, 1, 1, -1};
const int INF=0x3f3f3f3f;
const int N=1e6+10;
const int M=1010;
int n,m;
int mod,fa[N];
int Fpow(int b,int p){long long res=1;for(;p;p>>=1,b=b*b%mod)if(p&1)res=res*b%mod;return res;}
int qmi(ll a,ll k,ll p){ll res = 1;while (k) {if (k&1) res = res * a % p; k >>= 1;a = a * a % p;}return res;}
void init() {for(int i=1;i<=n;i++) fa[i]=i;}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void add(int a,int b) {int x=find(a);int y=find(b);fa[x]=y;}
bool ask(int a,int b) {return find(a)==find(b);}
const ull P =131;
ull h1[N],h2[2*N],p[2*N];
void getb(string s,char c,ull* h)   //初始化
{
	for (int i = 1; i <s.size(); i ++ )
	{
    	h[i] = h[i - 1] * P + (s[i] == c);
	}
}
int get(ull *h,int l, int r)   //计算哈希值
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
string a,b;

void solve()
{
    p[0]=1;
	cin>>n;
	cin>>a>>b;
	set<char>st(a.begin(),a.end());
	a=" "+a;
	b=" "+b+b;
	for(int i=1;i<N*2;i++)
	{
		p[i]=p[i-1]*P;
	}
	int ans = 0;
	for(char c:st){
		getb(a,c,h1);
		getb(b,c,h2);
		for(int i=1;i<=n;i++)
		{
			if(get(h2,i,i+n-1)==get(h1,1,n))
			{
				ans++;
				break;
			}
		}
	}
	cout<<ans<<endl;
	return;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

G、lxy的通风报信

bfs+prim最短路

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define endl '\n'
#define fi first
#define se second
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define lyh(i,a,b) for(int i=a;i<b;i++)
#define hyl(i,a,b) for(int i=a;i>b;i--)
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int ddx[8]={-1, 0, 1, 0, 1, -1, 1, -1};
const int ddy[8]={0, 1, 0, -1, -1, 1, 1, -1};
const int INF=0x3f3f3f3f;
const int N=2e5+10;
const int M=1010;
int n,m;
int mod,fa[N];
int Fpow(int b,int p){long long res=1;for(;p;p>>=1,b=b*b%mod)if(p&1)res=res*b%mod;return res;}
int qmi(ll a,ll k,ll p){ll res = 1;while (k) {if (k&1) res = res * a % p; k >>= 1;a = a * a % p;}return res;}
void init() {for(int i=1;i<=n;i++) fa[i]=i;}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void add(int a,int b) {int x=find(a);int y=find(b);fa[x]=y;}
bool ask(int a,int b) {return find(a)==find(b);}
char f[M][M];
int a[M][M];
int g[M][M];
int cnt = 0;
int ts = 1;
void bfs(int sx,int sy)
{
	queue<PII>q;
	q.push({sx,sy});
	vector<vector<int>>dist(1010,vector<int>(1010,0));
	vector<vector<int>>st(1010,vector<int>(1010,0));
	dist[sx][sy]=0;
	st[sx][sy]=1;
	ts = 1;
	while(!q.empty())
	{
		auto t = q.front();
		q.pop();
		int x = t.fi;
		int y = t.se;
		if(a[x][y]){
			g[a[sx][sy]][a[x][y]]=dist[x][y];
		}
		for(int i=0;i<4;i++)
		{
			for(int j=0;j<4;j++)
			{
				int nx = x+ddx[i];
				int ny = y+ddy[i];
				if(st[nx][ny]||nx<1||nx>n||ny<1||ny>m||f[nx][ny]=='#') continue;
				q.push({nx,ny});
				st[nx][ny]=1;
				if(f[nx][ny]=='*')
				{
					ts++;
				}
				dist[nx][ny] = dist[x][y]+1;
			}
		}
	}
}
int prim()
{
	vector<int>dis(1010,INF);
	vector<int>vis(1010);
	dis[1] = 0;
	int res = 0;
    for (int i =1;i<=cnt; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= cnt; j ++ )
            if (!vis[j] && (t == -1 || dis[t] > dis[j]))
                t = j;

        res += dis[t];
        vis[t] = true;
        for (int j = 1; j <= n; j ++ ) dis[j] = min(dis[j], g[t][j]);
    }
    return res;
}
void solve()
{
	cin>>n>>m;
	rep(i,1,n)
	{
		rep(j,1,m)
		{
			cin>>f[i][j];
			if(f[i][j] == '*')
			{
				a[i][j] = ++cnt;
			}
		}
	}
	
	rep(i,1,n)
	{
		rep(j,1,m)
		{
			if(a[i][j]){
				bfs(i,j);
				if(ts<cnt){
					cout<<"No"<<endl;
					return;
				}
			}
		}
	}
	cout<<prim()<<endl;
	
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

标签：const,CDEG,int,res,ll,long,2024,萌新,define
From： https://www.cnblogs.com/SonyaXu/p/18326003

相关文章

  • Camtasia2024最新版本怎么破解？最新Camtasia安装解锁特别版下载使用图文教程
    在这个视觉内容为王的时代，视频已经成为我们传递信息、分享故事和展示创意的首选方式。无论是教育工作者、企业培训师、内容创作者还是普通用户，都希望拥有一款功能强大、操作便捷的视频编辑软件，来将自己的想法和素材转化为精彩的视频作品。今天，我们要向您介绍的就是这样一款能够......
  • Camtasia Studio2024破解Crack中文永久激活版安装教程+汉化补丁
    在当今数字化内容盛行的时代，视频已经成为信息传递、知识分享和创意表达的重要形式。无论是教育工作者制作教学视频、企业员工进行培训内容创作，还是自媒体创作者展示创意作品，一款功能强大且易于使用的视频编辑软件都是必不可少的。今天，我们要为您介绍的就是这样一款备受瞩目的视......
  • 学习Java的第十一天啦（2024.7.26）
    1.死锁的条件：死锁的产生还涉及到一些具体的条件，这些条件可以被看作是死锁产生的必要条件，包括：1.互斥条件：资源不能被多个进程或线程同时访问，即资源是互斥的。2.请求保持条件：进程或线程在请求资源时，已经持有其他资源，并且不愿意释放已经持有的资源。3.不可剥夺条件：已经分配给进......
  • 2024年暑假ACM集训第1场
    A:小青蛙跳台阶题目描述想必你应该做过这么一道题：一只小青蛙一次可以跳1级台阶，也可以一次跳2级台阶。求该青蛙跳上第N级台阶总共有多少种跳法？（假设小青蛙的初始位置是第0级台阶）现在小青蛙遇到了一点麻烦，因为其中有一级台阶是坏的，小青蛙不能跳到这一级。假设坏掉的这一级台阶......
  • SMU Summer 2024 Contest Round 7
    BuyanInteger1.这题是二分答案，而不是公式拿来整除，以为是整除找了半天自己的错误，其实二分答案一发就能过。#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;typedefpair<int,int>pii;#definexfirst#defineysecond#defineall......
  • 2024暑假集训测试12
    前言比赛链接。T2其实和货车运输这题差不多但是由于给定图为树的部分分都没想出来压根没想到重构树，感觉不太应该，思路还是不清晰，赛时没有拿到那个部分分的，因为拿到的都顺着推出正解了；T3是道黑，赛时\(A,B\)循环输出能拿到\(40\)分，赛后重测了；T4题都看不懂。没挂分因为根......
  • 2024“钉耙编程”中国大学生算法设计超级联赛（3）
    Preface徐神是我们的红太阳，最后2min切了一道极难的string使得在这场前期爆炸的局面最后没有崩得太难看这场前期的开题顺序有点问题导致前5题出的很慢，中后期开始三人一人写一题，然后经典三开三卡好在最后我在WA了五发后写对拍把B过了，徐神又压线过了string，但比较可惜的......
  • 2024杭电第三场
    打了个爽！今天打得很稳，基本没有罚时，相当优雅的一场1001 考虑递推，发现答案和因子有关，再加上森林里只有一棵树的情况(i个节点构成的树的种数为f[i-1])#include<bits/stdc++.h>usingnamespacestd;constintN=1e6,mod=998244353;inlineintadd(intx,inty){return(x+=......
  • 2024中国工业互联网安全大赛智能家电行业赛道选拔赛
    流量分析的附件链接:https://pan.baidu.com/s/1UlWzfmsmRsZTR56FzXLuEg?pwd=6666提取码:6666恶意攻击流量描述：应用系统被植入了恶意后门，并从流量中识别其中的flag，提交格式:fag{XXXXXXXX}追踪这个流量解码过滤或者工具一把梭flag{39084EEF2D28E941F53E4A1AA1......
  • 2024牛客多校Bit Common & Bit More Common
    ABitCommon时间限制：3s(C++/C)/6s内存限制：1048576K(C++/C)/2097152K题目描述Giventwointegers\(n\)and\(m\),amongallthesequencescontaining\(n\)non-negativeintegerslessthan\(2^m\),youneedtocountthenumberofsuchsequences\(A\)tha......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99