链接：Dashboard - Educational Codeforces Round 161 (Rated for Div. 2) - Codeforces
A. Tricky Template
题意：给出a,b,c三个字符串，找出一个字符串t使得其与a、b匹配，不与c匹配；匹配的方式有，如果ti是小写字母，那么试图与他匹配的字符串s，si应该等于他；ti是大写字母，si应该不等于他。
思路：如果ai、bi都是相等的，那看c是否是相等，不是可以构造；ai不等于bi，看ci是否与其中一个相等，是可以构造，不是不行。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '
'
const int N = 1e5 + 10;
//const int mod = 998244353;
void solve()
{
int n;
cin>>n;
string a,b,c;
cin>>a>>b>>c;
bool flag=false;
for(int i=0;i<n;i++){
if(a[i]==b[i]){
if(c[i]==a[i]){
continue;
}
else flag=true;
}
else if(a[i]!=b[i]){
if(c[i]==a[i]||c[i]==b[i]){
continue;
}
else flag=true;
}
}
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
B. Forming Triangles
题意：有n条棍子，挑出三条组成一个合法的三角形，说明方案数量。
思路：题中说了不同的棍子长度的形式，是2^(ai)次方，说明只能做等边或者等腰，接下来只要统计各类长度有多少根，组合一下就可以。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define endl '
'
const int N = 1e5 + 10;
//const int mod = 998244353;
void solve()
{
int n;
cin>>n;
map<int,ll> q;
for(int i=1;i<=n;i++){
int x;
cin>>x;
q[x]++;
}
ll ans=0;
ll res=0;
for(auto it:q){
if(it.second>=3){
ans+=it.second*(it.second-1)*(it.second-2)/6;
}
if(it.second>=2){
ans+=it.second*(it.second-1)/2*res;
}
res+=it.second;
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
C. Closest Cities
题意：n个城市，给出他们在横轴上的坐标，当从一个城市前面离他最近的城市的代价为1，其他情况代价为俩者的距离，给出q个询问，求x和y的最近距离。
思路：从左从右跑俩遍前缀和，利用前缀和统计区间答案。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define endl '
'
const int N = 1e5 + 10;
//const int mod = 998244353;
bool check(vector<int> &a,int id){
int disl=(id==0?1e9+7:a[id]-a[id-1]);
int disr=(id+1==a.size()?1e9+7:a[id+1]-a[id]);
if(disl>disr){
return true;
}
else return false;
}
void solve()
{
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
vector<ll> pre(n),rev(n);
for(int i=1;i<n;i++){
pre[i]=pre[i-1]+(check(a,i-1)?1:a[i]-a[i-1]);
}
for(int i=n-2;i>=0;i--){
rev[i]=rev[i+1]+(!check(a,i+1)?1:a[i+1]-a[i]);
}
int q;
cin>>q;
while(q--){
int x,y;
cin>>x>>y;--x;--y;
if(x>y){
cout<<rev[y]-rev[x]<<endl;
}
else{
cout<<pre[y]-pre[x]<<endl;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
D. Berserk Monsters
题意：n只怪兽，各有攻击力和防御力，每轮会攻击彼此左右，当此轮受到的伤害大于防御力，死亡；询问每轮死亡怪物数量。
思路：直接模拟，走一遍计算死亡的，然后死亡的不进到下一个次队列里面，死亡的走一遍，修改死亡的怪物的左边的右边和右边的左边，方便下一次找左右，重复以上。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define endl '
'
const int N = 1e5 + 10;
//const int mod = 998244353;
void solve()
{
int n;
cin>>n;
vector<int> atk(n+2),def(n+2);
atk[0]=def[0]=atk[n+1]=def[n+1]=0;
queue<int> q;
for(int i=1;i<=n;i++){
cin>>atk[i];
q.push(i);
}
for(int i=1;i<=n;i++){
cin>>def[i];
}
vector<int> l(n+2),r(n+2);
for(int i=1;i<=n;i++){
l[i]=i-1;
r[i]=i+1;
}
vector<int> ans(n+1);
vector<int> book(n+1);
int len=0;
int cnt=0;
while(1){
int cnt=0;
vector<int> dead;
while(!q.empty()){
auto temp=q.front();
q.pop();
if(book[temp]>=1){
continue;
}
if(atk[l[temp]]+atk[r[temp]]>def[temp]){
dead.push_back(temp);
book[temp]++;
cnt++;
}
}
if(!cnt){
break;
}
set<int> s;
for(auto it:dead){
if(l[it]>=1){
r[l[it]]=r[it];
if(book[l[it]]>=1) continue;
else{
s.insert(l[it]);
}
}
if(r[it]<=n){
l[r[it]]=l[it];
if(book[r[it]]>=1) continue;
else{
s.insert(r[it]);
}
}
}
for(auto it:s){
q.push(it);
}
ans[++len]=cnt;
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
E. Increasing Subsequences
题意：给出x，要构造一个长度小于200的序列使得其中的上升子序列数量为x。
思路：当加入一个数小于前面所有数字的时候，序列上升子序列数量s不变；当大于的前面所有数字的时候的时候，s=s*2；由此递归回去算x的序列。详情可以看Educational Codeforces Round 161 Editorial - Codeforces
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define endl '
'
const int N = 1e5 + 10;
//const int mod = 998244353;
vector<int> f(ll x){
vector<int> res;
if(x==2){
res.push_back(0);
}
else if(x&1){
res=f(x-1);
res.push_back(*min_element(res.begin(), res.end()) - 1);
} else {
res = f(x / 2);
res.push_back(*max_element(res.begin(), res.end()) + 1);
}
return res;
}
void solve()
{
ll n;
cin>>n;
auto ans=f(n);
cout<<ans.size()<<endl;
for(auto it:ans){
cout<<it<<" ";
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
F. Replace on Segment
题意：对于一个序列a，序列元素从1到x；有操作取x，y，z，区间[x,y]中数字都不等于z，整个区间数字都变为z，求变为统一数字的最小操作次数。
思路：
ps：看的dalao的DP
dp1 i j k代表区间长度i、从j开始、全部为k的操作次数
dp2 i j k代表区间长度i、从j开始、全部不为k的操作次数
dp1[i][j][k]=min(self,dp1[x][j][k]+dp1[i-x][j+x][k]);dp2同理
dp1[i][j][k]=min(self,dp2[i][j][k]+1);
dp2[i][j][k]=min(self,dp2[i][j][others]);
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define endl '
'
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int n,m;
int dp1[105][105][105],dp2[105][105][105];//长度为i的区间在j位置开始，全（不）为k的最小修改次数
void solve()
{
cin>>n>>m;
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
vector<int> a(n+1);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<=n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<=m;k++){
dp1[i][j][k]=dp2[i][j][k]=1e9;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<=m;j++){
dp1[1][i][j]=(a[i]==j?0:1);
dp2[1][i][j]=(a[i]==j?1:0);
//cout<<dp1[1][i][j]<<" "<<dp2[1][i][j]<<endl;
}
}
for(int i=2;i<=n;i++){
for(int x=0;x+i-1<n;x++){
for(int y=1;y<=m;y++){
for(int j=1;j<i;j++){
dp1[i][x][y]=min(dp1[i][x][y],dp1[j][x][y]+dp1[i-j][x+j][y]);
dp2[i][x][y]=min(dp2[i][x][y],dp2[j][x][y]+dp2[i-j][x+j][y]);
dp1[i][x][y]=min(dp1[i][x][y],dp2[i][x][y]+1);
}
}
for(int y=1;y<=m;y++){
for(int j=1;j<=m;j++){
if(j==y){
continue;
}
dp2[i][x][y]=min(dp2[i][x][y],dp1[i][x][j]);
}
}
}
}
//cout<<dp1[3][0][3]<<endl;
int mx=0x3f3f3f3f;
for(int i=1;i<=m;i++){
mx=min(mx,dp1[n][0][i]);
}
cout<<mx<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}