nyist_acm 个人积分赛1（部分题解会补充）

2024-03-08 00:44
文章标签 补充 部分 个人 题解 积分 acm nyist

本文主要是介绍nyist_acm 个人积分赛1（部分题解会补充），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

这是一个博弈（废话）大家叫这种博弈为对称博弈

本题对称 博弈的特性如下：

  1. 对于给定的长度n我们可以先取中间的一段，使左右两边的白色方格一样多，
  2. 这样后手取其中一边，我们就可以在另一边取和他相同的长度，
  3. 这样我们是必赢的,因为不管奇数还是偶数个，我们可以取2或3使左右两边相等。
  4. 但是对于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;
}

这篇关于nyist_acm 个人积分赛1（部分题解会补充）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/785396。

相关文章

认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976： 题意： 在n场考试中，每场考试共有b题，答对的题目有a题。 允许去掉k场考试，求能达到的最高正确率是多少。 解析： 假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码： #include <iostream>#include <cstdio>#incl
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
HomeBank：开源免费的个人财务管理软件

HomeBank：开源免费的个人财务管理软件

在个人财务管理领域，找到一个既免费又开源的解决方案并非易事。HomeBank&nbsp;正是这样一个项目，它不仅提供了强大的功能，还拥有一个活跃的社区，不断推动其发展和完善。 开源免费：HomeBank 是一个完全开源的项目，用户可以自由地使用、修改和分发。用户友好的界面：提供直观的图形用户界面，使得非技术用户也能轻松上手。数据导入支持：支持从 Quicken、Microsoft Money
阅读更多...
C - Word Ladder题解

C - Word Ladder题解

C - Word Ladder 题解 解题思路： 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数（也就是需要变换多少次） 开始替换时： tips: 字符串下标以0开始 我们定义两个变量a和b，用于记录当前遍历到的字符 首先是判断：如果这时a已经==b了，那么就跳过，不用管； 如果a大于b的话：那么我们就让s中的第i项替换成b，接着就直接输出S就行了。 这样
阅读更多...
分布式系统的个人理解小结

分布式系统的个人理解小结

分布式系统：分的微小服务，以小而独立的业务为单位，形成子系统。 然后分布式系统中需要有统一的调用，形成大的聚合服务。 同时，微服务群，需要有交流（通讯，注册中心，同步，异步），有管理（监控，调度）。 对外服务，需要有控制的对外开发，安全网关。
阅读更多...
Java IO 操作——个人理解

Java IO 操作——个人理解

之前一直Java的IO操作一知半解。今天看到一个便文章觉得很有道理（ 原文章），记录一下。 首先，理解Java的IO操作到底操作的什么内容，过程又是怎么样子。          数据来源的操作： 来源有文件，网络数据。使用File类和Sockets等。这里操作的是数据本身，1,0结构。    File file = new File("path");   字
阅读更多...
笔记整理—内核！启动！—kernel部分（2）从汇编阶段到start_kernel

笔记整理—内核！启动！—kernel部分（2）从汇编阶段到start_kernel

kernel起始与ENTRY(stext)，和uboot一样，都是从汇编阶段开始的，因为对于kernel而言，还没进行栈的维护，所以无法使用c语言。_HEAD定义了后面代码属于段名为.head .text的段。         内核起始部分代码被解压代码调用，前面关于uboot的文章中有提到过（eg:zImage）。uboot启动是无条件的，只要代码的位置对，上电就工作，kern
阅读更多...
微积分-积分应用5.4（功）

微积分-积分应用5.4（功）

术语“功”在日常语言中用来表示完成一项任务所需的总努力量。在物理学中，它有一个依赖于“力”概念的技术含义。直观上，你可以将力理解为对物体的推或拉——例如，一个书本在桌面上的水平推动，或者地球对球的向下拉力。一般来说，如果一个物体沿着一条直线运动，位置函数为 s ( t ) s(t) s(t)，那么物体上的力 F F F（与运动方向相同）由牛顿第二运动定律给出，等于物体的质量 m m m 与其
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2