吳永輝教授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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275870.html
標籤：其他
上一篇：第七屆工程訓練大賽垃圾分類