AtCoder Beginner Contest 320
A - Leyland Number
思路:直接快速幂
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll qmi(ll a, ll b)
{
ll ans = 1;
while(b)
{
if(b & 1) ans = ans * a;
a = a * a;
b >>= 1;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
ll a,b;
cin>>a>>b;
cout<<qmi(a,b)+qmi(b,a)<<"\n";
return 0;
}
B - Longest Palindrome
思路:暴力枚举然后去\(check\)即可
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
string s;
cin>>s;
int sz = s.size();
s = "?"+s;
int ans = 1;
for(int i = 1;i <= sz; i++)
{
for(int j = 1;j <= sz-i+1; j++)
{
string t = s.substr(i,j);
string t2 = t;
reverse(t.begin(),t.end());
//cout<<t<<"\n";
//cout<<"i = "<<i<<" j = "<<j<<"\n";
if(t==t2)
{
ans = max(ans,j);
}
}
}
cout<<ans<<"\n";
return 0;
}
C - Slot Strategy 2 (Easy)
思路:贪心
考虑最不利的情况:每个转盘只出现同样的数字一次且在同一位置。这时候我们需要转动三圈才能使得都一样。
三重循暴力匹配即可。因为要是转三圈还是不行那么永远都不可能了。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
string s[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n;
cin>>n;
cin>>s[0]>>s[1]>>s[2];
int ans = 1<<30;
for(int i = 0;i <= n*3; i++)
for(int j = 0;j <= n*3; j++)
for(int k = 0;k <= n*3; k++)
if(i==j||i==k||k==j)continue;
else{
if(s[0][i%n]==s[1][j%n]&&s[1][j%n]==s[2][k%n])
ans = min(ans,max({i,j,k}));
}
if(ans==(1<<30))ans =-1;
cout<<ans<<"\n";
return 0;
}
D - Relative Position
思路:数据范围很小,直接暴力搜索。一开始还以为是拓扑序(cry).
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
vector<array<ll,3>>e[N*2];
pair<ll,ll>pos[N];
bool vis[N];
int n,m;
void dfs(int u,ll x,ll y)
{
pos[u]={x,y};
for(auto [v,xx,yy]:e[u])
{
if(!vis[v])
{
vis[v] = 1;
dfs(v,x+xx,y+yy);
}
}
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>m;
for(int i = 1;i <= m; i++)
{
ll a,b,x,y;
cin>>a>>b>>x>>y;
e[a].push_back({b,x,y});
e[b].push_back({a,-x,-y});
}
vis[1] = 1;
dfs(1,0,0);
for(int i = 1; i <= n; i ++)
{
if(vis[i])
cout<<pos[i].first<<" "<<pos[i].second<<"\n";
else
cout<<"undecidable\n";
}
return 0;
}
E - Somen Nagashi
思路:用\(set\)模拟。因为\(set\)自带排序功能,这样当一个人回来的时候,下标小的会放在前面。
考虑去维护\(2\)个\(set\),一个表示哪些在当前队伍里面,另一个表示出队的人(以回来时间为第一关键字,编号为第二关键字排序)。如果当前有出去的,判断在当前时刻有没有人回来的,如果回来的就插入第一个\(set\)里面。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n,m;
cin>>n>>m;
set<int>in;
set<pair<ll,int>>back;
for(int i = 1;i <= n; i++)
in.insert(i);
for(int i = 1;i <= m; i++)
{
int t,w,s;
cin>>t>>w>>s;
while(!back.empty())
{
auto x = *back.begin();
ll bt = x.first;
int id = x.second;
if(bt<=t)
{
back.erase(back.begin());
in.insert(id);
}else break;
}
if(!in.empty())
{
int now = *in.begin();
a[now] += w;
back.insert({t+s,now});
in.erase(in.begin());
}
}
for(int i = 1;i <= n; i++)
cout<<a[i]<<"\n";
return 0;
}
- Beginner AtCoder Contest ABCDE 320beginner atcoder contest abcde beginner atcoder contest 320 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 327