A. PENTA KILL!

题意:给定一个击杀序列,死亡不影响连杀,问是否有人完成五杀
分析:模拟,将每个选手的名字进行哈希,将属于每一个人的击杀序列处理出来,对每个人进行枚举判断即可
ac代码

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pb push_back
using namespace std;
int n,m,k,t;
int cnt;
unordered_map<string,int> mp;
int get(string & s)
{
	if(!mp[s]) mp[s] = ++ cnt;
	return mp[s];
}
int main()
{
	ios;
	cin >> n;
	vector<int> name[11];
	while(n --)
	{
		string a,b;
		cin >> a >> b;
		int xa = get(a),xb = get(b);
		name[xa].pb(xb);
	}
	

	bool success = false;
	for(int i = 1;i <= 10;i ++)
	{
		for(int j = 4;j < name[i].size();j ++)
		{
			set<int> s;
			for(int k = j - 4;k <= j;k ++) s.insert(name[i][k]);
			if(s.size() == 5) 
			{
				success = true;
				break;
			}
		}
		if(success) break;
	}

	if(success) cout << "PENTA KILL!" << endl;
	else cout << "SAD:(" << endl;
	return 0;
}

C. Jump and Treasure 单调队列优化dp + 调和级数

不懂 ,大爹队友写的
ac代码

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
const int N=1e6+5;
int a[N];
LL f[N],q[N],s[N];
int main()
{
	ios;
	int n,Q,p;
	cin>>n>>Q>>p;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		int m=n/i;
		int k=p/i;
		int hh=0,tt=0;
		q[0]=0;
		f[0]=0;
		for(int j=1;j<=m;j++)
		{
			while(q[hh]<j-k) hh++;
			f[j]=f[q[hh]]+a[i*j];
			while(hh<=tt&&f[q[tt]]<=f[j]) tt--;
			q[++tt]=j;
		}
		int temp=0;
		if((n+1-p)%i==0) temp=(n+1-p)/i;
		else temp=temp=(n+1-p)/i+1;
		while(q[hh]<temp) hh++;
		s[i]=f[q[hh]];
	}
	while(Q--)
	{
		int x;
		cin>>x;
		if(x>p) puts("Noob");
		else printf("%lld\n",s[x]);
	}
	return 0;
}

I. Cutting Suffix 思维

题意:将一个字符串的每个字母保留原有相对顺序分到两个集合里,要求让两个集合所对应的两个字符串的所有两两后缀的lcp之和最小
分析:
诈骗题:如果字符串中只有一种字符,则将一个字符放在一个集合里,其他的放另外一个,则所有lcp都是1,答案即为 |s|

  • 1,如果存在多个字符,则答案为0
    ac代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
//#define int long long
using namespace std;

typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,P = 13331,mod = 1e9 + 1;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-8;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
 
int n,m,k,t;

int main()
{
    ios;
    string s;
    cin >> s;
    vector<int> a(30);
    for(char c : s) a[c - 'a'] ++;
    int cnt = 0;
    for(int i = 0;i < 26;i ++) if(a[i]) cnt ++;
    if(cnt == 1) cout << s.size() - 1 << endl;
    else cout << 0 << endl;
    return 0;
}
 

J. Balanced Tree

题意:定义平衡二叉树为左右子树均为平衡二叉树,且左右子树大小差别不超1,给定n,求节点数为n的平衡二叉树的个数
分析:手玩几个样例可以发现答案是可以递推出来的递推式为

\[f(x)= \begin{cases} f(\frac{x – 1}{2}) * f(\frac{x – 1}{2} – 1) * 2, & \text {if $x$ is even} \\ f(\frac{x}{2}) * f(\frac{x}{2}), & \text{if $x$ is odd} \end{cases} \]

根据上式可以看出答案一定是2的整次幂,但乘法递推比较麻烦,我们用对数函数进行变形

\[g(x)= \begin{cases} g(\frac{x}{2}) + g(\frac{x}{2} – 1) + 1, & \text {if $x$ is even} \\ 2g(\frac{x – 1}{2}), & \text{if $x$ is odd} \end{cases} \]

我们记\(g(x) = a*g(\frac{x – 1}{2}) + b * g(\frac{x – 1}{2} – 1) + c\),则

\[g(x)= \begin{cases} a*[g(\frac{x}{2}) + g(\frac{x}{2} – 1)] + 2b * g(\frac{x – 1 – 1}{2}) + a + c, & \text {if $x$ is even} \\ 2a *g(\frac{x – 1}{2}) + b * [g(\frac{x – 1}{2}) + g(\frac{x – 1}{2} – 1)] + b + c & \text{if $x$ is odd} \end{cases} \]

\[= \begin{cases} a*g(\frac{x}{2}) + (a + 2b) * g(\frac{x}{2} – 1) + a + c, & \text {if $x$ is even} \\ (2a + b) *g(\frac{x – 1}{2}) + b * g(\frac{x – 1}{2} – 1) + b + c & \text{if $x$ is odd} \end{cases} \]

初始时我们令\(g(n) = 1 * g(\frac{n – 1}{2}) + 0 * g(\frac{n – 1}{2} – 1) + 0\)
\(n = 1\)时,\(g(1) = a*g(0) + b*g(-1) + c = c\)
然后每次除2根据奇偶判断改变系数的值,最终的c既是所求答案的幂次
所以$ans = 2 ^c \ mod \ 2^{64} \( 可以发现\)c >= 64$ 时,答案一定为0
ac 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
//#define int long long
using namespace std;

typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,P = 13331,mod = 1e9 + 1;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-8;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
 
int n,m,k,t;

void dfs(uLL x,uLL a,uLL b,uLL & c)
{
	if(x <= 1) return ;
	if(x & 1)
	{
		c += b;
		a = a + a + b;
		dfs((x - 1) / 2,a,b,c);
	}
	else
	{
		c += a;
		b = b + b + a;
		dfs(x / 2,a,b,c);
	}
}

int main()
{
	ios;
	cin >> t;
	while(t --)
	{
		uLL x;
		cin >> x;
		uLL c = 0;
		dfs(x,1,0,c);
		uLL ans = 1;
		if(c < 64) ans <<= c;
		if(c >= 64) cout << 0 << endl;
		else cout << ans << endl;
	}
	return 0;
}

K. aaaaaaaaaaA heH heH nuN 思维 + 二进制

题意:形如 nunhehheh + 若干个a 这种称为优雅串.
给定 n,构造恰好有 n 个子序列是优雅串的字符串
分析:我们仅考虑前缀nunhehheh后仅有n个a的字符串,可以发现这样的字符串所含优雅串的个数为
\(C_n^1 + C_n^2 + C_n^3 + C_n^4 + … + C_n^n = 2^n – 1\)
所以n个a对答案的贡献为\(2^n – 1\),看到这很容易想到数的二进制表示,我们求出所给数字n的最高位1的位数,用这么多a去表示,当二进制中为1时我们在a的倒数该位数个a前加一个h
最后,我们离答案还差x个,x为n的二进制表示中1的个数,这个只要在最后一个a前面补x个h即可
ac代码

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
int n,m,k,t;
string f(int n)
{
	string res;
	while(n) res += char('0' + n % 2),n /= 2;
	reverse(all(res));
	return res;
}

int main()
{
	ios;
	cin >> t;
	while(t --)
	{
		cin >> n;
		if(n == 0)
		{
			cout << "nunhehheh" << endl;
			continue;
		}
		if(n == 1)
		{
			cout << "nunhehheha" << endl;
			continue;
		}
		//cout << f(n) << endl;
		int cnt ,idx = 0,x = 0;
		vector<int> bin;
		for(int k = 0;k <= 31;k ++) if(n >> k & 1) bin.pb(k),cnt = k,x ++;
		string res,tp;
		for(int i = 0;i < cnt;i ++)
		{
			
			if(idx < bin.size() && i == bin[idx]) res += 'h',idx ++;res += 'a';
		}
		idx = 0;
		while(res[idx] == 'h') idx ++;
		idx ++;
		while(x --) tp += 'h';
		res = res.substr(0,idx) + tp + res.substr(idx);
		reverse(all(res));
		cout << "nunhehheh" << res << endl;
	}
	return 0;
}

L. Collecting Diamonds

题意:
• 长度为 n 的只含有 ABC 的字符串.
• 选择连续的三个位置 ABC,如果 A 在奇数位置就删去 AC;否则删去 B.
• 最大化操作数.
思路:
• 注意到如果操作删除 B 则当前 ABC 组不可能继续操作,并
且也只有删除 B 才能更改后面的 ABC 组的奇偶性.
• 所以应该尽量让每个组都操作一次删除 B,并尽量保证在操
作删除 B 之前删除尽量多的 AC.
• 所以使用一个变量存储下前面一共删除了几次 B,便可以用
以计算可以删除多少个 AC.
ac代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
//#define int long long
using namespace std;

typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,P = 13331,mod = 1e9 + 1;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-8;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
 
int n,m,k,t;

int main()
{
    string s;
    cin >> s;
    n = s.size();
    s = ' ' + s + ' ';
    vector<int> p(n + 1);
    vector<bool> st(n + 1);
    for(int i = 1;i <= n;i ++)
    {
        if(s[i] == 'B')
        {
             for(int j = 1;;j ++)
             {
                 if(s[i - j] != 'A' || s[i + j] != 'C')
                 {
                     if(j != 1)
                     {
                         p[i] = j - 1;
                         st[i] = true;
                     }
                     break;
                 }
             }
            
        }
    }
    
    int ans = 0,cnt = 0;
    for(int i = 1;i <= n;i ++)
    {
        if(s[i] == 'B' && st[i])
        {
            if(!cnt)
            {
                if(i & 1)
                {
                    cnt ++,ans ++;
                }
                else
                {
                    if(p[i] == 1) ans ++;
                    else  cnt ++ ,ans += 2;
                }
                continue;                
            }
            
        
            ans += min(p[i],(i % 2 == 0) + cnt + 1);
            cnt ++;
        }
        
    }
    cout << ans << endl;
    return 0;
}
 

原文地址:http://www.cnblogs.com/notyour-young/p/16792942.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性