吴永辉教授2021年讲课7-9题解

吴永辉教授2021年讲课7-9题解

1.我写的是A-D和V

2.张同学写的E-H，代翻为博客

3.曲同学写的 I-L@Arctique~

4.@，M张同学写的（M-P）{
M题题解
N题题解
O题解
P题题解
}

5.郭同学写的Q-T和U，代翻为博客

大家都很认真呐呐呐~

A题直达
代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;
typedef long long ll;
const int MAX_N=1e5+5;
const int inf=0x3f3f3f3f;
int a[MAX_N];
int sum;
int cnt;
int main(){
	int n;
	int i=1;
	int l=1;
	while(cin>>n&&n>0){
		a[0]=n;
		while(cin>>a[i]&&a[i]){
			l++;
			i++;
		}
		sort(a,a+l);
		for(int j=0;j<l;j++){
			for(int s=j;s<l;s++){
				if(a[s]==2*a[j]){
					sum++;
					break;
				}
			}
		}
		cout<<sum<<endl;
		sum=0;i=1;l=1;
	} 
	return 0;
}

B题直达
题意：九键号码盘，输入字母或数字，统计相同的号码出现的次数，出现一次的忽略不计
题解：我的思路大概就是把一个字符串变成一个7位数！！
sort一下，弄个循环，记录一下次数再输出就可
思路有点笨

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int num[N];
int sum;
int cnt;
char s[N][101];
int main(){
	int n;
	cin>>n;
	getchar();
	for(int i=0;i<n;i++){
		cin>>s[i];
		for(int j=0;s[i][j]!='\0';j++){
			if(s[i][j]=='-')continue;
			if(s[i][j]>='A'&&s[i][j]<='C')
				num[i]=num[i]*10+2;
			else if(s[i][j]>='D'&&s[i][j]<='F')
				num[i]=num[i]*10+3;
			else if(s[i][j]>='G'&&s[i][j]<='I')
				num[i]=num[i]*10+4;
			else if(s[i][j]>='J'&&s[i][j]<='L')
				num[i]=num[i]*10+5;
			else if(s[i][j]>='M'&&s[i][j]<='O')
				num[i]=num[i]*10+6;
			else if(s[i][j]>='P'&&s[i][j]<='S')
				num[i]=num[i]*10+7;
			else if(s[i][j]>='T'&&s[i][j]<='V')
				num[i]=num[i]*10+8;
			else if(s[i][j]>='W'&&s[i][j]<='Y')
				num[i]=num[i]*10+9;
			else{
				num[i]=num[i]*10+s[i][j]-'0';
			}
		}
	}
	sort(num,num+n);
//	for(int i=0;i<n;i++){
//		debug(num[i]);
//	}
	int flag=0;
	int j;
	for(int i=0;i<n;i++){
		int cnt=1;
		for(j=i+1;j<n;j++){
			if(num[i]==num[j])cnt++;
			else break;
		}
		if(cnt>1){
			printf("%03d-%04d %d\n",num[i]/10000,num[i]%10000,cnt);
			flag=1;
			i=j-1;
		}
	}
	if(flag==0)printf("No duplicates.\n");
	return 0;
}

运行结果：

12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279
310-1010 2
487-3279 4
888-4567 3

C题直达
题解：全排列即可，有用到next_permutation函数
代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
	string s;
	while(cin>>s){
		sort(s.begin(),s.end());//对字符串s按照字典序排序
		cout<<s<<endl;//输出第一个
		while(next_permutation(s.begin(),s.end())){//输出字典序比第一个大的其他字符串
			cout<<s<<endl;
		}
	} 
	return 0;
}

D题直达
题目大意：
就是说魔术师要穿墙表演，一次表演最多能穿k个墙。一共有n行墙在map上放置，下面n行是墙的第一块和最后一块砖的左上角的坐标。然后让我们判断最少去掉几堵墙能使魔术师从上往下任意挑选一列都能穿墙成功。

思路：从当前超过k堵墙的列开始，到墙的末尾，最长的墙对整个墙的布局的影响最大。所以就拆这个所谓最长的墙。

#include<bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;
typedef long long ll;
const int N=1e3+5;
const int inf=0x3f3f3f3f;
const double pi=acos(-1);
int sum;
int ans;
int cnt;
struct node {
	int beginx,beginy;//起始位置
	int endx,endy;//结束位置
} a[201];
int c[201];
int main() {
    int t;
    int n,k;
    int max_;
    int tempr;
    int tempid;
    int tempc;
    scanf("%d",&t);
    while(t--)
    {
        max_=-1;
        ans=0;
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&a[i].beginx,&a[i].beginy,&a[i].endx,&a[i].endy);
            if(a[i].beginx>a[i].endx)//因为题目没有说给的坐标一定是末尾在后
                swap(a[i].beginx,a[i].endx);
            if(max_<a[i].endx)
                max_=a[i].endx;//这里就是记录所有的墙中最靠右的右端点
        }
        memset(c,false,sizeof(c));//这个c数组是记录每一列有多少个墙
        for(int i=0;i<n;i++)
        {
            for(int j=a[i].beginx;j<=a[i].endx;j++)
                c[j]++;
        }
        for(int i=0;i<=max_;i++)
        {
            if(c[i]<=k)//如果当前列的墙的个数小于k，那么就继续循环
                continue;
            tempc=c[i]-k;//否则，tempc记录这一列多了多少堵墙
            while(tempc--)
            {
                tempr=-1;//这个是用来记录墙的长度最长的那个墙的右端点
                for(int j=0;j<n;j++)
                {
                    if(a[j].beginx<=i&&a[j].endx>=i&&tempr<a[j].endx)//这里就是说，我们要找的要拆的墙必须是i列被包含在其中，并且右端点是最靠右的（也就是从当前列开始墙的长度是最长的那堵墙）
                    {
                        tempr=a[j].endx;//记录所谓最长的墙的右端点
                        tempid=j;//记录最长的墙的位置（也就是这堵墙是哪一行的）
                    }
                }
                for(int j=a[tempid].beginx;j<=a[tempid].endx;j++)//我们拆掉第tempid行的墙，然后影响的列的墙数也要相应改变
                {
                    c[j]--;
                }
                a[tempid].endx=-1;//被拆的那行墙要pass掉
                ans++;//到这里已经拆掉了一堵墙，然后结果加1
            }
        }
        printf("%d\n",ans);
    }
	return 0;
}

V题直达
大概题意：
找出公共单词数

思路：dp加最长公共子序列
这个题可能后台数据有问题，一直没过去，但是代码应该没问题，有问题的话我再改改哈

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int dp[1010][1010];
string s1,s2;
struct node {
	int num;
	string word[1010];
} t1,t2;
void devide(string s,node &t) { //
	int len=s.size();
	t.num=1;
	for(int i=0; i<1000; i++){
		t.word[i].clear();
	}
	
	for(int i=0; i<len; i++) {
		if((s[i]>='A'&&s[i]<='Z')||s[i]>='a'&&s[i]<='z'||s[i]>='0'&&s[i]<='9')
			t.word[t.num]+=s[i];//
		else
			t.num++;
	}
	int cnt=0;
	for(int i=1; i<=t.num; i++)
		if(!t.word[i].empty())
			t.word[++cnt]=t.word[i];
	t.num=cnt;
}
int main() {
	int cas=1;
	while(!cin.eof()) {
		getline(cin,s1);
		getline(cin,s2);
		printf("%2d. ",cas++);
		if(s1.empty()||s2.empty()) {
			printf("Blank!\n");
			continue;
		}
		devide(s1,t1);
		devide(s2,t2);
		for(int i=0; i<=t1.num; i++)
			dp[i][0]=0;
		for(int j=0; j<=t2.num; j++)
			dp[0][j]=0;
		for(int i=1; i<=t1.num; i++)
			for(int j=1; j<=t2.num; j++)
				if(t1.word[i]==t2.word[j])
					dp[i][j]=dp[i-1][j-1]+1;
				else
					dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		printf("Length of longest match: %d\n",dp[t1.num][t2.num]);
	}
	return 0;
}