2022.3.2
题单地址:https://codeforces.com/contest/988
目录
A. Diverse Team【模拟】
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],st[N],n,k;
vector<int>ve;
int main(void)
{
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
if(!st[a[i]]) ve.push_back(i+1);
if(ve.size()==k) break;
st[a[i]]++;
}
if(ve.size()==k)
{
puts("YES");
for(int i=0;i<ve.size();i++) cout<<ve[i]<<" ";
}else puts("NO");
return 0;
}
B. Substrings Sort【暴力枚举】
先按长度从小到大排序，然后在判断当前字符串的的子串有没有上一个字符串
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
string s[N];
int n;
bool cmp(string a,string b){return a.size()<b.size();}
int main(void)
{
cin>>n;
for(int i=0;i<n;i++) cin>>s[i];
sort(s,s+n,cmp);
for(int i=1;i<n;i++)
{
int m=s[i].size();
bool flag=0;
for(int len=1;len<=m;len++)
{
for(int j=0;j+len<=m;j++)
{
string temp=s[i].substr(j,len);
if(temp==s[i-1]) flag=1;
}
}
if(!flag)
{
puts("NO");
return 0;
}
}
puts("YES");
for(int i=0;i<n;i++) cout<<s[i]<<endl;
return 0;
}
C. Equal Sums【哈希表】
注意开long long
求每一行的和。
然后枚举每一行，删除一个数后的值，存一下。
如果已经存过了，且不是同一行，那么说明找到了。
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
typedef pair<int,int> PII;
const int N=1e5*4+10;
vector<LL>ve[N];
LL k,n,x,s[N];
unordered_map<LL,PII>mp;
int main(void)
{
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d",&n);
for(int j=0;j<n;j++) scanf("%d",&x),ve[i].push_back(x),s[i]+=x;
}
for(int i=1;i<=k;i++)
{
for(int j=0;j<ve[i].size();j++)
{
x=s[i]-ve[i][j];
if(mp.count(x)&&mp[x].first!=i)//存在，且不是同一行
{
puts("YES");
auto temp=mp[x];
cout<<temp.first<<" "<<temp.second<<endl;
cout<<i<<" "<<j+1;
return 0;
}
mp[x]={i,j+1};
}
}
puts("NO");
return 0;
}
D. Points and Powers of Two【数学结论题 + 暴力枚举】
由上可知，答案的最大长度为3，且相邻两项的差是固定的。
故可以直接枚举首相和差。找到最长的答案即可。
注意开long long，注意剪枝枚举前三项即可。找到一个长度未3的结果就可以直接不用找了。
特别需要注意的是用map,用哈希表会超时，这是因为在枚举的时候查找如果没有则会创建到哈希表里，而建哈希表的结点是十分耗时间的。
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1e5*4+10;
map<LL,int>mp;
LL a[N],b[N],n;
vector<LL>ans;
int main(void)
{
cin>>n;
for(int i=0;i<n;i++) scanf("%lld",&a[i]),mp[a[i]]++;
for(int i=0,k=1;i<=30;i++,k*=2) b[i]=k;
sort(a,a+n);
for(int i=0;i<n;i++)
{
vector<LL>ve; ve.push_back(a[i]);
if(ans.size()==3) break;
for(int k=0;k<=30;k++)
{
vector<LL>temp=ve;
LL tempx=temp[0];
while(mp[tempx+b[k]])
{
tempx=tempx+b[k];
temp.push_back(tempx);
if(temp.size()==3) break;
}
if(temp.size()>ans.size()) ans=temp;
if(ans.size()==3) break;
}
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
return 0;
}
E. Divisibility by 25【贪心】
能背25整除的结尾无非四种情况
- 以25结尾
- 以50结尾
- 以75结尾
- 以00结尾
大致思路枚举四种情况找到最小的步数，从后往前找找到第一个数将其移到指定位置。再找第二个数将其移到指定位置。
需要注意的是，这时候可能有前导0，这时候再从前到后的找到一个非零的数将其移到开头。
/*25
50
75
00
*/
#include<bits/stdc++.h>
using namespace std;
string s;
int ans=1e9;
void solve(char a,char b)
{
int index=0,flag=0,cnt=0;
for(int i=s.size()-1;i>=0;i--)
{
if(s[i]==b)
{
index=i,flag=1;
break;
}
}
if(!flag) return;
while(index+1<s.size()) swap(s[index],s[index+1]),index++,cnt++;
index=0,flag=0;
for(int i=s.size()-2;i>=0;i--)
{
if(s[i]==a)
{
index=i,flag=1;
break;
}
}
if(!flag) return;
while(index+1<s.size()-1) swap(s[index],s[index+1]),index++,cnt++;
index=0,flag=0;
for(int i=0;i<s.size()-2;i++)//解决前导0
{
if(s[i]!='0')
{
index=i,flag=1;
break;
}
}
while(index-1>=0) swap(s[index],s[index-1]),index--,cnt++;
if(s[0]=='0') return;
ans=min(ans,cnt);
}
int main(void)
{
cin>>s;
string temp=s;
solve('2','5'); s=temp;
solve('5','0'); s=temp;
solve('7','5'); s=temp;
solve('0','0'); s=temp;
if(ans==1e9) puts("-1");
else cout<<ans;
return 0;
}
F. Rain and Umbrellas【DP】
状态表示: dp[i]表示从[0-i]的疲劳度
对于这种区间问题我们一般这样表示rain[i] 表示 [i,i+1]这一段区间 这样的话便于处理。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long int LL;
int a,n,m;
LL rain[N],w[N],dp[N];
int main(void)
{
cin>>a>>n>>m;
while(n--)
{
int l,r; cin>>l>>r;
for(int i=l;i<=r-1;i++) rain[i]=1;
}
while(m--)
{
LL x,c; cin>>x>>c;
if(!w[x]) w[x]=c;
else w[x]=min(w[x],c);
}
for(int i=0;i<=a;i++) dp[i]=1e18;
dp[0]=0;
for(int i=1;i<=a;i++)
{
if(!rain[i-1]) dp[i]=dp[i-1];//说明这一段区间是无雨的
else//有雨
{
for(int j=0;j<i;j++)
if(w[j]) dp[i]=min(dp[i],dp[j]+(i-j)*w[j]);
}
}
if(dp[a]==1e18) puts("-1");
else cout<<dp[a];
return 0;
}