Educational Codeforces Round 161 (Rated for Div. 2)
A. Tricky Template
思路:
貌似只要想到了就可以,我是记录了一下字符串c和字符串a和b之间的满足数,如果等于n表示一定不存在,否则就是存在的
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin>>n;
string s1,s2,s3;
cin>>s1;
cin>>s2;
cin>>s3;
// strig s4="";
int ans=0;
for(int i=0;i<n;i++){
if(s1[i]!=s2[i]){
if(s3[i]==s1[i]||s3[i]==s2[i]){
ans++;
}
}
if(s1[i]==s2[i]){
if(s3[i]==s1[i]){
ans++;
}
}
}
if(ans==n){
cout<<"NO"<<endl;
return ;
}
cout<<"YES"<<endl;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin >> t; while(t--)
solve();
return 0;
}
B. Forming Triangles
思路:
因为每根长度都是2的ai次方,因此保证了三角形不会出现三个边不一样的,最后用组合数算一下就行
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
int a[N];
int C(int x,int y){
int ans1=1;
int ans2=1;
for(int i=x,j=y;j>=1;i--,j--){
ans1*=i;
ans2*=j;
}
return ans1/ans2;
}
void solve() {
int n;
cin>>n;
int ans=0;
memset(a,0,sizeof a);
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[x]++;
}
int k=0;
for(int i=0;i<=n;i++){
if(a[i]>=3){
ans+=C(a[i],3);
}
if(a[i]>=2){
ans+=C(a[i],2)*k;
// k+=a[i];
}
k+=a[i];
}
cout<<ans<<endl;
return ;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin >> t; while(t--)
solve();
return 0;
}
C. Closest Cities
思路:
感觉这个比b要好想,前缀和的应用,只需要改一下其中加的是绝对值还是1就好了,然后正着求一次,反着求一次
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N];
int s1[N];
int s2[N];
int v[N];
void solve() {
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
if(i==1){
v[i]=i+1;
// cout<<v[i]<<" ";
continue;
}
if(i==n){
v[i]=i-1;
// cout<<v[i]<<" ";
continue;
}
v[i]=(a[i]-a[i-1])>a[i+1]-a[i]?i+1:i-1;
// cout<<v[i]<<" ";
}
// cout<<endl;
for(int i=1;i<=n;i++){
if(i==1){
s1[i]=0;
// cout<<s1[i]<<" ";
continue;
}
// s1[i]=s1[i-1]+(v[i-1]==i?1:(v[i]-v[i-1]));
// cout<<s1[i]<<" ";
if(v[i-1]==i){
s1[i]=s1[i-1]+1;
}
else{
s1[i]=s1[i-1]+(a[i]-a[i-1]);
}
// cout<<s1[i]<<" ";
}
cout<<endl;
for(int i=n;i>=1;i--){
if(i==n){
s2[i]=0;
// cout<<s2[i]<<" ";
continue;
}
s2[i]=s2[i+1]+(v[i+1]==i?1:(a[i+1]-a[i]));
// cout<<s2[i]<<" ";
}
int m;
cin>>m;
while(m--){
int x,y;
cin>>x>>y;
if(y>=x){
cout<<s1[y]-s1[x]<<endl;
}
else{
cout<<s2[y]-s2[x]<<endl;
}
}
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin >> t; while(t--)
solve();
return 0;
}
标签:Educational,Rated,cout,int,Codeforces,long,cin,--,solve
From: https://www.cnblogs.com/du463/p/17974349