Mirrored String II
看到题解说是马拉车算法,我赛时并没想到(好吧其实我是比赛完才知道有马拉车这个算法)
因为字符串的长度只有1000,直接暴力跑其实就可以了,但是要注意的是;回文串有俩种形式,一种是aba的另一种是baab的形式,这是需要注意的地方
//#pragma GCC optimize(3) //O2优化开启
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<string>
#include<algorithm>
//#include<unordered_map>
#include<map>
#include<bitset>
#include<cstring>
//#include <unordered_set>
//#include<priority_queue>
#include<queue>
#include<deque>
#include<set>
#include<stdlib.h>
#define dbug cout<<"*****hear*****"<<endl;
#define rep(a,b,c) for(ll a=b;a<=c;a++)
#define per(a,b,c) for(ll a=b;a>=c;a--)
#define no cout<<"No"<<endl;
#define yes cout<<"Yes"<<endl;
//#define endl "\n"//交互题一定要关!!!!!!!!!
#define lowbit(x) (x&-x)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//priority_queue<int,vector<int>,greater<int> >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> PII;
typedef pair<long double, long double> PDD;
ll INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// int get_len(int x1,int y1,int x2,int y2)
// {
// return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
// }
const ll N = 2e5 + 10;
const ll mod1 = 998244353;
const ll mod2 = 1e9 + 7;
const ll hash_num = 3e9 + 9;
ll n, m, ca;
ll arr[N], brr[N], crr[N], drr[N];
//ll h[N],ne[N],e[N],w[N],book[N],idx;
// void add(ll a, ll b , ll c)
// {
// e[idx] = b, w[idx] = c,ne[idx] = h[a], h[a] =idx ++ ;
// }
vector<ll>ve[N];
bool check(char x)
{
if (x=='A'||x == 'H' || x == 'I' || x == 'M' || x == 'O' || x == 'T' || x == 'U' || x == 'V' || x == 'W' || x == 'X' || x == 'Y')
return 1;
return 0;
}
void solve()
{
string s;
cin >> s;
ll len = s.size();
rep(i, 0, len)
{
arr[i] = 0, brr[i] = 0;
}
rep(i, 0, len - 1)
{
if (check(s[i]))
{
arr[i] = 1;
ll l = i - 1;
ll r = i + 1;
while (l >= 0 && r < len)
{
if (check(s[l]) && s[r] == s[l])
{
l--;
r++;
arr[i] += 2;
}
else
{
break;
}
}
if (check(s[i+1] ) && s[i] == s[i + 1])
{
brr[i] = 2;
ll l = i - 1;
ll r = i + 2;
while (l >= 0 && r < len)
{
if (check(s[l]) && s[r] == s[l])
{
l--;
r++;
brr[i] += 2;
}
else
{
break;
}
}
}
}
}
sort(arr, arr + len);
sort(brr, brr + len);
cout << max(arr[len - 1], brr[len - 1]) << endl;;
}
int main()
{
IOS;
ll _;
_ = 1; //scanf("%lld",&_);
cin >> _;
ca = 1;
while (_--)
{
solve();
ca++;
}
return 0;
}
Competitive Seagulls
这是一个博弈(废话)大家叫这种博弈为对称博弈
本题对称 博弈的特性如下:
- 对于给定的长度n我们可以先取中间的一段,使左右两边的白色方格一样多,
- 这样后手取其中一边,我们就可以在另一边取和他相同的长度,
- 这样我们是必赢的,因为不管奇数还是偶数个,我们可以取2或3使左右两边相等。
- 但是对于2和3不同,只有这两种情况我们是先手必输的。
void solve()
{
cin >> n;
if(n==2 || n==3)
{
cout << "second" << endl;
}
else
{
cout << "first" << endl;
}
}
Hey JUDgE
每次输入的长度只有7个,而比赛需要的题目数量是5,所以最多只能组合俩次题目,又因为题目不能重复利用,新得到的题目也无法再次组合,所以就直接枚举就可以找到答案
//#pragma GCC optimize(3) //O2优化开启
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<string>
#include<algorithm>
//#include<unordered_map>
#include<map>
#include<bitset>
#include<cstring>
//#include <unordered_set>
//#include<priority_queue>
#include<queue>
#include<deque>
#include<set>
#include<stdlib.h>
#define dbug cout<<"*****hear*****"<<endl;
#define rep(a,b,c) for(ll a=b;a<=c;a++)
#define per(a,b,c) for(ll a=b;a>=c;a--)
#define no cout<<"No"<<endl;
#define yes cout<<"Yes"<<endl;
//#define endl "\n"//交互题一定要关!!!!!!!!!
#define lowbit(x) (x&-x)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//priority_queue<int,vector<int>,greater<int> >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> PII;
typedef pair<long double, long double> PDD;
ll INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// int get_len(int x1,int y1,int x2,int y2)
// {
// return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
// }
const ll N = 2e5 + 10;
const ll mod1 = 998244353;
const ll mod2 = 1e9 + 7;
const ll hash_num = 3e9 + 9;
ll n, m, ca;
ll arr[N], brr[N], crr[N], drr[N];
//ll h[N],ne[N],e[N],w[N],book[N],idx;
// void add(ll a, ll b , ll c)
// {
// e[idx] = b, w[idx] = c,ne[idx] = h[a], h[a] =idx ++ ;
// }
ll book[N];
ll get_hard(char a)
{
brr['A'] = 1;
brr['B'] = 2;
brr['C'] = 3;
brr['D'] = 4;
brr['E'] = 5;
return brr[a];
}
void solve()
{
string s;
cin >> s;
map<ll, ll>mp;
rep(i, 0, s.size() - 1)
{
mp[get_hard(s[i])] ++;
arr[i + 1] = get_hard(s[i]);
}
ll num = 0;
rep(i, 1, 5)
{
// cout << arr[i] << " ";
if (!mp[i])num++;
}
if (num == 0)
{
cout << "YES" << endl;
return;
}
ll xx;
ll yy = 0;
rep(i, 1, 7)
{
rep(j, i + 1, 7)
{
xx = 1;
mp[arr[i]]--, mp[arr[j]]--, mp[arr[i] + arr[j]]++;
rep(k, 1, 5)
{
if (!mp[k])xx = 0;
}
mp[arr[i]]++, mp[arr[j]]++, mp[arr[i] + arr[j]]--;
if (xx == 1)yy = 1;
}
}
if (!yy)
{
rep(i, 1, 7)
{
rep(j, i + 1, 7)
{
rep(k, 1, 7)
{
rep(l, k + 1, 7)
{
xx = 1;
if (i == k || j == l || i == l || j == k)continue;
mp[arr[i]]--, mp[arr[j]]--, mp[arr[i] + arr[j]]++;
mp[arr[k]]--, mp[arr[l]]--, mp[arr[k] + arr[l]]++;
rep(mm, 1, 5)
{
if (!mp[mm])xx = 0;
}
mp[arr[i]]++, mp[arr[j]]++, mp[arr[i] + arr[j]]--;
mp[arr[k]]++, mp[arr[l]]++, mp[arr[k] + arr[l]]--;
if (xx == 1)
{
// cout << i << " " << j << " " << k << " " << l << endl;
yy = 1;
}
}
}
}
}
}
if (yy)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
int main()
{
IOS;
ll _;
_ = 1; //scanf("%lld",&_);
cin >> _;
ca = 1;
while (_--)
{
solve();
ca++;
}
return 0;
}
Smooth Developer
很水的一个模拟,但是,诶,您没猜到吧我从开始接触到正式ac前后跨了4h。
唯一需要注意的就是所需要的函数要全部标记完之后再输出,而不是有一个输出一个
//#pragma GCC optimize(3) //O2优化开启
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<string>
#include<algorithm>
//#include<unordered_map>
#include<map>
#include<bitset>
#include<cstring>
//#include <unordered_set>
//#include<priority_queue>
#include<queue>
#include<deque>
#include<set>
#include<stdlib.h>
#define dbug cout<<"*****hear*****"<<endl;
#define rep(a,b,c) for(ll a=b;a<=c;a++)
#define per(a,b,c) for(ll a=b;a>=c;a--)
#define no cout<<"No"<<endl;
#define yes cout<<"Yes"<<endl;
//#define endl "\n"//交互题一定要关!!!!!!!!!
#define lowbit(x) (x&-x)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//priority_queue<int,vector<int>,greater<int> >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> PII;
typedef pair<long double, long double> PDD;
ll INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// int get_len(int x1,int y1,int x2,int y2)
// {
// return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
// }
const ll N = 2e5 + 10;
const ll mod1 = 998244353;
const ll mod2 = 1e9 + 7;
const ll hash_num = 3e9 + 9;
ll n, m, ca;
ll arr[N], brr[N], crr[N], drr[N];
//ll h[N],ne[N],e[N],w[N],book[N],idx;
// void add(ll a, ll b , ll c)
// {
// e[idx] = b, w[idx] = c,ne[idx] = h[a], h[a] =idx ++ ;
// }
map<string, ll>mp;
vector<ll>ve[N];
char x[30], s[N][30];
ll book[N];
void dfs(ll u)
{
book[u] = 1;
for (auto it : ve[u])
{
if (book[it])continue;
dfs(it);
}
}
void solve()
{
scanf("%lld%lld", &n, &m);
rep(i, 1, n)ve[i].clear();
mp.clear();
rep(i, 1, n)
{
scanf("%s", s[i]);
mp[s[i]] = i;
ll num;
scanf("%lld", &num);
rep(j, 1, num)
{
scanf("%s", x);
if (mp[x] != i)
{
ve[i].push_back(mp[x]);
}
}
}
memset(book, 0, sizeof book);
while (m--)
{
scanf("%s", x);
if(!book[mp[x]])dfs(mp[x]);
}
rep(i, 1, n)
{
if (book[i])
{
printf("%s\n", s[i]);
}
}
}
int main()
{
//IOS;
ll _;
_ = 1; scanf("%lld", &_);
//cin >> _;
ca = 1;
while (_--)
{
solve();
ca++;
}
return 0;
}
ACPC Headquarters : AASTMT (Stairway to Heaven)
换个想法,我们不抓着比赛名称看,我们就抓着志愿者看,数据很小只有365,当得知一个志愿者有需要参加的比赛的时候,就遍历一遍是否有矛盾的,存在矛盾的储存下来就OK了
//#pragma GCC optimize(3) //O2优化开启
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<string>
#include<algorithm>
//#include<unordered_map>
#include<map>
#include<bitset>
#include<cstring>
//#include <unordered_set>
//#include<priority_queue>
#include<queue>
#include<deque>
#include<set>
#include<stdlib.h>
#define dbug cout<<"*****hear*****"<<endl;
#define rep(a,b,c) for(ll a=b;a<=c;a++)
#define per(a,b,c) for(ll a=b;a>=c;a--)
#define no cout<<"No"<<endl;
#define yes cout<<"Yes"<<endl;
//#define endl "\n"//交互题一定要关!!!!!!!!!
#define lowbit(x) (x&-x)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//priority_queue<int,vector<int>,greater<int> >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> PII;
typedef pair<long double, long double> PDD;
ll INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// int get_len(int x1,int y1,int x2,int y2)
// {
// return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
// }
const ll N = 2e5 + 10;
const ll mod1 = 998244353;
const ll mod2 = 1e9 + 7;
const ll hash_num = 3e9 + 9;
ll n, m, ca;
ll arr[N], brr[N], crr[N], drr[N];
//ll h[N],ne[N],e[N],w[N],book[N],idx;
// void add(ll a, ll b , ll c)
// {
// e[idx] = b, w[idx] = c,ne[idx] = h[a], h[a] =idx ++ ;
// }
map < string, vector<PII>>mp;
set<string >se;
void solve()
{
cin >> n;
mp.clear();
se.clear();
rep(i, 1, n)
{
string name;
ll l, r, num;
cin >> name >> l >> r >> num;
rep(j, 1, num)
{
string pename;
cin >> pename;
for (ll k = 0;k < mp[pename].size();k++)
{
if (mp[pename][k].first <= l && l <= mp[pename][k].second)
{
se.insert(pename);
}
else if (mp[pename][k].first <= r && mp[pename][k].second >= r)
{
se.insert(pename);
}
else if (l <= mp[pename][k].first && r >= mp[pename][k].second)
{
se.insert(pename);
}
}
mp[pename].push_back({ l,r });
}
}
cout << se.size() << endl;
for (auto it : se)
{
cout << it << endl;
}
}
int main()
{
IOS;
ll _;
_ = 1; //scanf("%lld",&_);
cin >> _;
ca = 1;
while (_--)
{
solve();
ca++;
}
return 0;
}