A. Two Elevators
思路:
直接模拟即可,要注意每个abs要分开算,罚时爆炸~
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
const int N = 110,M = N * 2,INF = 0x3f3f3f3f;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int,int>PII;
void solve()
{
int a,b,c;cin >> a >> b >> c;
int x = abs(a - 1),y = abs(c - b) + abs(c - 1);
if(x > y)cout << 2 << endl;
else if(x < y)cout << 1 << endl;
else if(x == y)cout << 3 << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
B. Decode String
思路:
这道题我们倒着推,碰到零那么前面两个数一定和自己是一起的
刚开始正着写巨麻烦…
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
const int N = 110, M = N * 2, INF = 0x3f3f3f3f;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int, int>PII;
void solve()
{
int n; cin >> n;
string s; cin >> s;
string res;
for(int i = s.size() - 1; i >= 0; i --)
{
if(s[i] == '0')
{
res += 'a' + ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') - 1);
i -= 2;
}
else res += 'a' + (s[i] - '0' - 1);
}
reverse(res.begin(),res.end());
cout << res << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
C. Jumping on Tiles
思路:
从首个字母跳到最后一个字母的最小代价是一定的,要想使跳的次数最多,我们只需要选在这两个字母之间的
即可,这样就不会增加代价了,简单的模拟一下就好了.想复杂了,代码写的巨丑
求代价的部分直接算就行了,不想改了~
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
const int N = 110, M = N * 2, INF = 0x3f3f3f3f;
typedef long long LL;
//#define int long long
#define endl "\n"
typedef pair<int, int>PII;
void solve()
{
string s;cin >> s;
if(s.size() == 2)
{
cout << abs(s[1] - s[0]) << " " << 2 << endl;
cout << 1 << " " << 2 << endl;
return;
}
vector<PII>q;
for(int i = 1; i < s.size() - 1; i ++)
if((s[i] >= s[0] && s[i] <= s[s.size() - 1]) || (s[i] <= s[0] && s[i] >= s[s.size() - 1]))
q.push_back({s[i] - 'a' + 1,i + 1});
if(s[0] >= s[s.size() - 1])sort(q.begin(),q.end(),greater<PII>());
else sort(q.begin(),q.end());
int res = 0;
if(q.size() == 0)res += abs((s[s.size() - 1] - 'a' + 1) - (s[0] - 'a' + 1));
else
{
for(int i = 0; i < q.size(); i ++)
{
if(i == 0) res += abs(q[i].first - (s[0] - 'a' + 1));
else res += abs(q[i].first - q[i - 1].first);
}
res += abs((s[s.size() - 1] - 'a' + 1) - q[q.size() - 1].first);
}
cout << res << " " << q.size() + 2 << endl;
if(q.empty())
{
cout << 1 << " " << s.size() << endl;
return;
}
cout << 1 << " ";
for(auto x : q)
cout << x.second << " ";
cout << s.size() << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
D. Friends and the Restaurant
思路:
首先与预处理出每个人的代价,我们只是想让分的组数最多,不难发现两个正数一定是可以分到一起的
但为了最大化,对于每个正数看是不是能和一个负数进行匹配,这样才是最多的.
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#pragma GCC optimize(3)
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int, int>PII;
int a[N],b[N];
void solve()
{
//要求的是每组的b之和大于等于每组的a之和
int n;cin >> n;
for(int i = 0; i < n; i ++)cin >> a[i];
for(int i = 0; i < n; i ++)cin >> b[i];
priority_queue<int,vector<int>,greater<int>>p;
priority_queue<int>q;
int cnt = 0;
for(int i = 0; i < n; i ++)
{
int t = b[i] - a[i];
if(t >= 0)
{
p.push(t);
cnt ++;
}
else q.push(t);
}
int res = 0;
while(!p.empty() && !q.empty())
{
int t = p.top();p.pop();
int x = q.top();
if(t + x >= 0)
{
cnt --;res ++;
q.pop();
}
}
cout << res + cnt / 2 << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
E. Guess the Cycle Size
思路:
对于一个闭环,如果两个点之间的有两条不同的路径,那么就说明这两个点位于环的两端
首先1肯定在一端,我们只需要枚举另一端即可
#include<queue>
#include<string>
#include<iostream>
#include<cmath>
#include<map>
#include<algorithm>
//#define O2 #pragma GCC optimize(2)
#define endl "\n"
using namespace std;
#define int long long
signed main()
{
for(int i = 1; i <= 25; i ++)
{
int t1,t2;
cout << "? " << 1 << " " << i + 1 << endl;
cin >> t1;
if(t1 == -1)
{
cout << "! " << i << endl;
return 0;
}
cout << "? " << i + 1 << " " << 1 << endl;
cin >> t2;
if(t1 != t2)
{
cout << "! " << t1 + t2 << endl;
return 0;
}
}
return 0;
}