A PENTA KILL!
题意：给定一个击杀序列 判断是否有一个人连续击杀五个不同的人
分析：
开始很容易走到一个误区 出现连续相同的就舍去从零开始计数
但是比如 A C B C A D 遇到两个C 舍去从零开始 但是实际上 可以是后面四个组成
数据允许n方 所以枚举每个五杀开头 判断能否成立即可
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=2e3+5;
int n,cnt,pd;
string s[maxn],t[maxn];
map<string,int>mp;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i]>>t[i];
for(int i=1;i<=n;i++){
if(pd)break;
set<string>Q;
Q.insert(t[i]);
for(int j=i+1;j<=n;j++){
if(s[i]!=s[j])continue;
if(Q.find(t[j])!=Q.end())
break;
else Q.insert(t[j]);
if(Q.size()==5)pd=1;
}
}
if(pd)cout<<"PENTA KILL!"<<endl;
else cout<<"SAD:("<<endl;
return 0;
}
C. Jump and Treasure
题意：
分析：
很容易写出方程 dp[i]=max(dp[j])+q[i] 暴力转移肯定会超时
求这种连续滑动的最大最小值可以用单调队列优化
#include <bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(false);
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f;
const ll MAXN = 1e6 + 10;
ll n, q, p;
struct Node
{
ll val, pos;
} a[MAXN];
ll dp[MAXN];
int main()
{
cin >> n >> q >> p;
for (int i = 1; i <= n; ++i)
{
cin >> a[i].val;
a[i].pos = i;
}
while (q--)
{
ll x;
cin >> x;
if (x > p)
{
cout << "Noob" << endl;
continue;
}
dp[0] = 0;
vector<ll> v;
v.push_back(0);
for (int i = x; i <= n; i += x)
{
v.push_back(i);
}
v.push_back(n + 1);
deque<ll> dq;
dq.push_back(0);
for (int i = 1; i < v.size(); ++i)
{
while (dq.size() && v[i] - dq.front() > p)
dq.pop_front();
dp[v[i]] = dp[dq.front()] + a[v[i]].val;
while (dq.size() && dp[dq.back()] < dp[v[i]])
dq.pop_back();
dq.push_back(v[i]);
}
cout << dp[n+1]<< endl;
}
return 0;
}
I. Cutting Suffix
题意：
签到题没啥说的
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
string s;
int main(){
cin>>s;
int len=s.size();
int pd=1;
for(int i=1;i<s.size();i++)
if(s[i]!=s[0]){
pd=0;break;
}
if(pd)cout<<len-1<<endl;
else cout<<0<<endl;
return 0;
}
J. Balanced Tree
题意：
分析：
#define ll unsigned long long int
ll dfs(ll x, ll a, ll b, ll c)
{
if (x == 0) return 0;
if (x == 1) return c;
if (x & 1) return dfs(x >> 1, a * 2 + b, b, c + b);
else return dfs(x >> 1, a, a + b * 2, c + a);
}
int main()
{
IOS;
int T; cin >> T;
while (T--)
{
ll ans = 1;
ll n; cin >> n;
ll c = dfs(n, 1, 0, 0);
if (c >= 64) ans = 0;
else ans <<= c;
cout << ans << endl;
}
return 0;
}
K. aaaaaaaaaaA heH heH nuN
题意：
分析：
好气啊 明明思路和题解一模一样 但是我写出来就是re
#include<bits/stdc++.h>
using namespace std;
int cnt[42];
typedef long long ll;
ll pow2[40];
void init()
{
pow2[0]=1;
for(int i=1;i<=31;i++)
pow2[i]=pow2[i-1]*2;
return;
}
int main(){
init();
int t;
cin>>t;
while(t--){
int n,ans=0;
cin>>n;
for(int i=31;i>0;i--)
cnt[i]=0;
for(int i=31;i>0;i--)
{
if(n>=pow2[i])
{
cnt[i]++;
n-=(pow2[i]);
cnt[1]++;
}
}
if(n%2)
cnt[1]++;
cout<<"nunhehhe";
for(int i=31;i>0;i--)
{
for(int j=0;j<cnt[i];j++)
cout<<"h";
cout<<"a";
}
cout<<"\n";
}
}