|
题解若有错误，欢迎指正，q私法我或直接评论皆可
能力有限，暂时只有A到F，后期有所突破会更新g题h题
1.A.Square String?
题目链接：https://codeforces.com/contest/1619/problem/A
大致题意：
如果一个字符串在一行中被写了两次，那么这个字符串就叫做square，
判断一个字符串是不是square
思路：
很明显，判断前半部分与后半部分是否相同即可
特别的，如果字符串长度为奇数，必然不是
#include <bits/stdc++.h>
using namespace std;
void solve()
{
string s;
cin>>s;
int num=0;
int l=s.size();
if(l%2==1) cout<<"no"<<endl;
else
{
for(int i=0;i<l/2;i++)
{
if(s[i]!=s[i+l/2])
{
cout<<"no"<<endl;
num=1;
break;
}
}
if(num==0) cout<<"yes"<<endl;
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
2.Squares and Cubes
题目链接：https://codeforces.com/contest/1619/problem/B
大致题意：
给定一个数n；让你找到从1到n的所有的平方数与立方数的个数；
思路1：
分别计算出平方数与立方数的个数，num1,num2，显然其中有一部分数同时是平方数和立方数，比如64，是8的平方或者4的立方；
那么我们要做的便是找出同时是平方数与立方数的个数num3;
最后的答案便是num1+num2-num3;
既是平方数又是立方数的数，就是6次方数
m^3，如果m是平方数，那么
m^3就是6次方数，所以对1到num2的三次方数中，又是平方数的个数为对num2开方，就是6次方数的个数
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
int num1=sqrt(n);
int num2=0;
for(int i=1;i<=n/i;i++)
{
if(pow(i,3)<=n&&pow(i+1,3)>n) num2=i;
}
int num3=sqrt(num2);
cout<<num1+num2-num3<<endl;
}
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
system("pause");
return 0;
}
思路二：给定的n的范围1e9，直接暴力
在set中每个元素的值都唯一，也就是插入n个1，里面只会有一个1；
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
set<int> a;
for (int i = 1; i * i <= n; i++)
a.insert(i * i);
for (int i = 1; i * i * i <= n; i++)
a.insert(i * i * i);
cout << a.size() << endl;
}
3.C. Wrong Addition
题目链接：https://codeforces.com/contest/1619/problem/C
题意：
有这样一种特殊的加法，a+b=c不进位，12+9=111
第一步，她把a的最后一位和b的最后一位相加，然后把它们的和写在答案里。
在接下来的每一步中，她都会对相同位置的每一对数字进行相同的操作，并将结果写在答案的左边。
现在给你a和c，让你求b
思路：直接模拟，c的最后一位如果比a的最后1位大，直接减去即可
若是小，要向前借位，这个时候要注意，如果前面的那位数不为1，则b不存在
最后如果c有剩余全部加在b的后面，最后将字符串b翻转即可；
#include <bits/stdc++.h>
using namespace std;
void solve()
{
string a,b,c;
cin>>a>>c;
int len1=a.size()-1;
int len2=c.size()-1;
int ok=1;
for(int i=len1;i>=0;i--)
{
if(len2<0)
{
ok=0;
break;
}
int x=a[i]-'0',y=c[len2]-'0';
if(y>=x)
{
b+=y-x+'0';
len2--;
}
else
{
if(!len2||c[len2-1]!='1')
{
ok=0;
break;
}
b+=(10+y-x)+'0';
len2-=2;
}
}
while(len2>=0) b+=c[len2--];
if(ok==0) cout<<"-1"<<endl;
else
{
while(!b.empty()&&b.back()=='0') b.pop_back();
if(b.empty()) cout<<"-1"<<endl;
else
{
reverse(b.begin(),b.end());
cout<<b<<endl;
}
}
}
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
system("pause");
return 0;
}
，
4.New Year’s Problem
题目链接：https://codeforces.com/contest/1619/problem/D
大致题意：有m个商店和n个朋友，最多只能去n-1个商店
第j个朋友从礼物中获得aj个单位的快乐。α=min{a1,a2，…，an}。目标是买礼物，使α的值尽可能大；
思路：我们要使每一个ai都尽可能的大
①当某些人获得的最大快乐值在同一个商店时，最多去n-1个商店的限制相当于就没了，我们对每个人取得的最大快乐值取min就行
②当每个人获得的最大值都在不同的商店时，其中有一个商店肯定要选两个，那么我们要选择第二个值最大的商店买两个人的礼物，再与除去这两人的最大快乐取min
因此每个人的最大快乐与每个商店第二大的最大值值取min就是答案
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int main(){
int t;
cin >> t;
for (int i = 0; i < t; i++){
int m, n;
cin >> m >> n;
vector<vector<int>> p(m, vector<int>(n));
for (int j = 0; j < m; j++){
for (int k = 0; k < n; k++){
cin >> p[j][k];
}
}
int ans = 0;
for (int j = 0; j < m; j++){
vector<int> p2 = p[j];
sort(p2.begin(), p2.end(), greater<int>());
ans = max(ans, p2[1]);
}
for (int j = 0; j < n; j++){
int mx = 0;
for (int k = 0; k < m; k++){
mx = max(mx, p[k][j]);
}
ans = min(ans, mx);
}
cout << ans << endl;
}
}
E. MEX and Increments
题目链接：https://codeforces.com/contest/1619/problem/E
大致题意：
给定一个长度为n的序列，对于从0到n的i，需要多少次操作才可以使i为最小的自然数；
操作为，对于一个数+1；
思路：
先将这个序列从小到大排列：
对于从0到n的i值：
要使，最小自然数为i，我们首先需要将所有的i操作＋1一次；
我们再考虑有没有i-1，如果没有i-1，那么小于i-1的数是否有多余的，有多余的我们就可以对这个多余的数操作多次得到i-1，没有多余的，则说明对于从i开始的所有数，不存在操作使最小自然数为i，i+1，…n;
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N];
int cnt[N];
long long ans[N];
void solve()
{
memset(ans,-1,sizeof(ans));
memset(a,0,sizeof(a));
memset(cnt,0,sizeof(cnt));
int n;cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
cnt[a[i]]++;
}
sort(a,a+n);
stack <int> st;
long long sum=0;
for(int i=0;i<=n;i++)
{
if(i>0&&cnt[i-1]==0)
{
if(st.empty())break;
int j=st.top();
st.pop();
sum+=i-j-1;
}
ans[i]=sum+cnt[i];
while(i>0&&cnt[i-1]>1)
{
cnt[i-1]--;
st.push(i-1);
}
}
for(int i=0;i<=n;i++) cout<<ans[i]<<' ';
cout<<endl;
}
int main()
{
int t ; cin>>t;
while(t)
{
solve();
t--;
}
return 0;
}
F. Let’s Play the Hat?
题目链接：https://codeforces.com/contest/1619/problem/F
大致题意：有m个桌子，n个人玩k局游戏，每个桌子坐n/m向上取整或者向下取整个数的人，使所有人坐上n/m向上取整人数桌子的次数相差不超过一次；
思路：将所有人看成一个循环即可，比如5 2 2；
大桌子坐3人，小桌子坐2人，
第一轮游戏 1，2，3 大桌子 4，5小桌子
看成一个循环，那么第二局初始状态为4 5 1 2 3
第二局游戏 4 5 1大桌子 2 3小桌子
（n-1/m）+1就是n/m向上取整的值
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n, m, k;
cin >> n >> m >> k;
vector<int> p(n);
forn(i, n)
p[i] = i;
if (tt > 0)
cout << endl;
forn(round, k)
{
int index = 0;
forn(table, m) {
int size = n / m;
if (table < n % m)
size++;
cout << size;
forn(j, size)
cout << " " << p[index++] + 1;
cout << endl;
}
rotate(p.begin(), p.begin() + (n % m) * ((n + m - 1) / m), p.end());
}
}
}
|