Living-Dream 系列笔记 第21期

Problem

T1

/*
思路：枚举二元组(i,j)，依次检验k次训练课，若i的位置总是>j或<j，则将答案累加。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int k,n,ans;
int a[31][31];

signed main(){
	ios::sync_with_stdio(0);
	cin>>k>>n;
	for(int i=1;i<=k;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			bool f1=1,f2=1;
			for(int x=1;x<=k;x++){
				int p1,p2;
				for(int y=1;y<=n;y++) if(a[x][y]==i) p1=y;
				for(int y=1;y<=n;y++) if(a[x][y]==j) p2=y;
				if(p1>p2){ f1=0; break; } 
			}
			for(int x=1;x<=k;x++){
				int p1,p2;
				for(int y=1;y<=n;y++) if(a[x][y]==i) p1=y;
				for(int y=1;y<=n;y++) if(a[x][y]==j) p2=y;
				if(p2>p1){ f2=0; break; } 
			}
			if(f1||f2)
				//cout<<i<<' '<<j<<'\n';
				ans++;
		}
	}
	cout<<ans;
	return 0;
}

T2

/*
思路：
1.对于求绿色，直接将guess[]与ans[]比较即可，顺便求出每个品种的奶牛的绿色个数；
2.对于求黄色，遍历guess[]，对于每一头新品种的牛，分别求出它在guess[]和ans[]中出现的次数，对这两个值-绿色个数取min即为当前奶牛的黄色个数，不要忘记标记这个品种。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int vis[131],flag[131];
char guess[31][31],ans[31][31];

int get_green(){
	int cnt=0;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(guess[i][j]==ans[i][j])
				cnt++,flag[guess[i][j]]++;
	return cnt;
}
int get_yellow(){
	int cnt=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			char now=guess[i][j];
			
			int s1=0,s2=0;	
			for(int x=0;x<3;x++)
				for(int y=0;y<3;y++)
					s1+=(guess[x][y]==now);
			for(int x=0;x<3;x++)
				for(int y=0;y<3;y++)
					s2+=(ans[x][y]==now);
			
			if(s1&&s2&&!vis[now]){
				//cout<<now<<'\n';
				cnt+=min(s2-flag[now],s1-flag[now]),vis[now]=1;
				//break;
			}
		}
	}
	return cnt;
}

signed main(){
	ios::sync_with_stdio(0);
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			cin>>guess[i][j];
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			cin>>ans[i][j];
	cout<<get_green()<<'\n';
	cout<<get_yellow();
	return 0;
}

T3

/*
思路：使用一个deque维护所有操作即可。
坑点：else总是和最近的if配对，因此需要勤加大括号！
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int s,now=1;
deque<int> dq;

signed main(){
	ios::sync_with_stdio(0);
	cin>>s;
	while(s--){
		char op1,op2; int k;
		cin>>op1>>op2;
		if(op1=='A'){
			if(op2=='L') dq.push_front(now++);
			else dq.push_back(now++);
		}
		else{
			cin>>k;
			if(op2=='L'){
			    for(int i=1;i<=k;i++) 
                    if(!dq.empty()) dq.pop_front();
            }
			else{
				for(int i=1;i<=k;i++) 
                    if(!dq.empty()) dq.pop_back();
            }
		}
	}
	while(!dq.empty())
		cout<<dq.front()<<'\n',dq.pop_front(); 
	return 0;
}

T4

/*
思路：
通过观察样例可知，S'排序后就是n个构造串排序后的首字母，
而每个构造串的首字母就是末字母的下一个字母，
因此我们用sorted[]保存S'排序后的字母序列，
并且维护cur表示S'中的当前位置，
然后倒序确认答案字母，
从S'[p]开始不断在sorted[]中寻找与S'[cur]相等的字母下标x,令cur=x，
此时的S'[cur]即为下一个字母，放入ans数组即可。
*/
#include<bits/stdc++.h>
using namespace std;

int n,p,cur;
bool vis[10031];
char s[10031],sorted[10031],ans[10031];

int main(){
    cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i],sorted[i]=s[i];
	cin>>p;
    sort(sorted+1,sorted+n+1);
    
    ans[1]=s[p];
    for(int i=1;i<=n;i++)
        if(sorted[i]==s[p]){
            cur=i; break;
        }
    
    for(int i=n;i>=2;i--){
        ans[i]=s[cur],vis[cur]=1;
        for(int j=n;j>=1;j--)
            if(sorted[j]==s[cur]&&!vis[j]){
                cur=j; break;
            }
    }
    
    for(int i=1;i<=n;i++) cout<<ans[i];
    return 0;
}