目录
- A. Hard Way
- B. Power Walking
- C. Great Sequence
- D. Repetitions Decoding
A. Hard Way
题意：
给定一个三角形，若从y = 0上任意一点，无法通过线段到达三角形边上（线段不能通过三角形内部），计算这种边的总长度。
题解：
当且仅当，三角形上面的边是平行于x轴的情况下，存在答案。这条边的长度即为答案。
代码：
void slove()
{
int T; cin>>T;
while(T--)
{
ll x1, y1, x2, y2, x3, y3; cin>>x1>>y1>>x2>>y2>>x3>>y3;
if(y1 == y2 && y3 < y2) cout<<abs(x2-x1)<<endl;
else if(y1 == y3 && y2 < y1) cout<<abs(x1-x3)<<endl;
else if(y2 == y3 && y1 < y3) cout<<abs(x2-x3)<<endl;
else cout<<0<<endl;
}
}
B. Power Walking
题意： 给定一个数组。将该数组分为 k组（1 <= k <= n），每组的价值为不同数字的个数。计算每个 k对应的所有组的总价值的最小值。
题解：
每次分组都先把独立存在的数分出去。记原数组中不同数字的个数为cnt。当 k <= cnt时，答案为 cnt； 当 k > cnt 时，答案为 cnt++。
代码：
void slove()
{
int T; cin>>T;
while(T--)
{
int n; cin>>n;
map<int, int> mp;
mp.clear();
int cnt = 0;
for(int i = 0; i < n; i++)
{
int x; cin>>x;
if(!mp[x]) cnt++, mp[x] = 1;
}
for(int i = 1; i <= n; i++)
{
if(i <= cnt) cout<<cnt<<" ";
else cnt++, cout<<cnt<<" ";
}
cout<<endl;
}
}
C. Great Sequence
题意： 给定一个数组和一个 x。当一个数组中一半的数乘以x后对应的数，是该数组的另一半数时称为 great sequence。你可以在原数组中一次插入任意一个数，问最少需要插入几次能使得原数组成为great sequence。
题解：
统计原数组中的数，且其倍数为 x的数也在数组中的个数。剩下的个数就是最终答案。（好绕…）。记得开 ll
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "n"
#define IOS ios::sync_with_stdio(false); cin.tie(0)
#define inf 0x3f3f3f3f
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define debug(a) cout<<"tdebug:"<<a<<endl
const double PI = acos(-1.0);
const int mod = 998244353;
const int eps = 1e-8;
const int N = 10 + 2e5;
void slove();
template<typename T>void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-') f *= -1; ch = getchar();}
while(isdigit(ch)){x = x*10+ch-48; ch = getchar();} x *= f;
}
template<typename T>void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x >= 10) print(x/10);
putchar(x % 10 + '0');
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS;
slove();
return 0;
}
ll a[N];
void slove()
{
int T; cin>>T;
while(T--)
{
ll n, x; cin>>n>>x;
map<ll, ll> mp;
mp.clear();
for(int i = 0; i < n; i++)
{
cin>>a[i];
mp[a[i]]++;
}
ll cnt = 0;
for(auto i:mp)
{
if(mp[i.first] > 0 && mp[i.first*x] > 0)
{
ll minn = min(mp[i.first], mp[i.first*x]);
mp[i.first] -= minn, mp[i.first*x] -= minn, cnt += 2*minn;
}
}
cout<<n-cnt<<endl;
}
}
D. Repetitions Decoding
题意：
给定一个数组，每次可以在数组的任一位置插入两个相同的数，数也是任意的。定义 123123这种序列为 tandem repeats。输出最终使得原数组成为 tandem repeats的过程中，操作的总次数，每次在哪个位置，插入什么值。并且输出最终数组中，每一部分为 tandem repeats的连续子段的长度。
题解：
从前往后遍历数组。假设当前位置为 i，则在它后面的位置找到位置 j，使得 a[j] == a[i]。然后将 i到 j之间的数字，不断地插入 j后面的位置（每在后面插入一次值，下次插入位置就向后加1）。最终就能得到一个 tandem repeats。注意一下输出格式。
示例：
1 3 1 2 2 3
1 3 1 3 3 2 2 3（在第二个 1后面插入 3 3，这时前面的1 3 1 3已经是 tandem repeats了）
1 3 1 3 3 2 2 3 2 2 （在第二个 3后面插入 2 2）
1 3 1 3 3 2 2 3 2 2 2 2 （在上一次插入位置的下一位置插入 2 2）
这时整个数组已经是 tandem repeats了，能分为 3部分：[1 3 1 3] 、[3 2 2 3 2 2]、 [2 2]
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "n"
#define IOS ios::sync_with_stdio(false); cin.tie(0)
#define inf 0x3f3f3f3f
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define debug(a) cout<<"tdebug:"<<a<<endl
#define for1(i, a, b) for(int i = a; i <= b; i++)
#define for2(i, b, a) for(int i = b; i >= a; i--)
const double PI = acos(-1.0);
const int mod = 998244353;
const int eps = 1e-8;
const int N = 10 + 2e5;
void slove();
template<typename T>void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-') f *= -1; ch = getchar();}
while(isdigit(ch)){x = x*10+ch-48; ch = getchar();} x *= f;
}
template<typename T>void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x >= 10) print(x/10);
putchar(x % 10 + '0');
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS;
slove();
return 0;
}
void slove()
{
int T; cin>>T;
while(T--)
{
int n; cin>>n;
int a[N];
map<int, int> mp;
for1(i, 1, n)
{
cin>>a[i];
mp[a[i]]++;
}
int f = 0;
for(auto i:mp)
{
if(mp[i.first]&1)
{
cout<<"-1"<<endl;
f = 1;
break;
}
}
if(f) continue;
vector<pii> ans;
ans.clear();
vector<int> ans2;
ans2.clear();
mp.clear();
int idx = 1;
for1(i, 1, n)
{
for1(j, i+1, n)
{
if(a[j] == a[i])
{
idx = j;
for1(k, i+1, j-1)
{
for2(x, n, idx+1) a[x+2] = a[x];
n += 2;
a[idx+1] = a[idx+2] = a[k];
ans.push_back(make_pair(idx, a[k]));
idx++;
}
ans2.push_back(idx-i+1);
i = idx; //后面有 i++
break;
}
}
}
cout<<ans.size()<<endl;
for(auto x:ans) cout<<x.first<<" "<<x.second<<endl;
if(ans.size() == 0)
{
cout<<n/2<<endl;
for1(i, 1, n/2) cout<<2<<" ";
cout<<endl;
}
else
{
cout<<ans2.size()<<endl;
for(auto i : ans2) cout<<i<<" ";
cout<<endl;
}
}
}
最后
以上就是神勇果汁最近收集整理的关于Codeforces Round #773 (Div. 2)（ＡＢＣＤ）A. Hard WayB. Power WalkingC. Great SequenceD. Repetitions Decoding的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。
发表评论 取消回复