問題 A: 小h的訊息加密
題目描述
小h最近看了諜戰電影，對里面訊息的加密方式很感興趣，他決定和朋友試一試，小h給朋友兩個序列，兩個序列的最長公共單調遞增子序列就是要傳遞的訊息，有時候序列太長了，小h的朋友找不出來，所以他找到了你
輸入
第一個數字n表示序列長度
后面兩行每行n個數字表示小h給出的兩個序列
(n<=1000)
輸出
輸出需要傳遞的原序列的長度
樣例輸入
3
1 2 3
3 1 2
樣例輸出
2
提示
需要傳遞的是1 2這個子序列
思路
這是公共遞增子序列問題，最樸素的演算法是O(n^3) dp[i][j]表示以b[j]結尾的公共子序列
如果a[i]==b[j]那答案就是a[i]和b[j]匹配接在dp[i-1][k]后（k小于j且b[k]<b[j]）
? 至于為什么是dp[i-1]呢，因為dp[i-1][k]必定比dp[i-x][k](x>1)更優
如果a[i]!=b[j]那答案就是dp[i-1][j]，不要a[i]嘛
PS：當然n的范圍是1000的話n3就是109肯定會超時的
O(n3)代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
int a[1005],b[1005],dp[1005][1005];
int main()
{
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)scanf("%d",&b[i]);
for(int i=1;i<=n;++i){
int num=0;
for(int j=1;j<=n;++j){
if(a[i]==b[j]){
dp[i][j]=1;
for(int k=1;k<j;++k){
if(b[k]<b[j]&&dp[i-1][k]+1>dp[i][j]){
dp[i][j]=dp[i-1][k]+1;
}
}
}else{
dp[i][j]=dp[i-1][j];
}
}
}
int ans=0;
for(int i=1;i<=n;++i)ans=max(ans,dp[n][i]);
printf("%d\n",ans);
return 0;
}
n^3會超時那考慮優化一維前兩維很明顯是不能優化的，必須列舉所有情況，那只能從第三維入手
列舉第二維的時候維護最長的能接在b[j]前的不就可以了
用一個臨時陣列num存比在b[j]前比b[j]小的最長公共遞增子序列長度
那第三維就可以省略了，
當然因為dp的時候狀態至于前一列狀態有關，甚至可以將dp陣列轉成一維，不過意義不大，在這就不寫了
O(n2)代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int a[1005],b[1005],dp[1005][1005];
int main()
{
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)scanf("%d",&b[i]);
for(int i=1;i<=n;++i){
int num=0;
for(int j=1;j<=n;++j){
dp[i][j]=dp[i-1][j];
if(a[i]>b[j]&&num<dp[i-1][j])num=dp[i-1][j];//b[k]比a[i]小就取dp[i-1][k]的最大值
if(a[i]==b[j])dp[i][j]=num+1;//當a[i]==b[j],num取的是比a[i]小的b[k]那自然b[j]>b[k]
}
}
int ans=0;
for(int i=1;i<=n;++i)ans=max(ans,dp[n][i]);
printf("%d\n",ans);
return 0;
}
問題 B: 小h的數列Ⅱ
題目描述
有一個初始長度為0的數列，三種操作
1.將某一個元素插入
2.將某一個元素洗掉
3.查詢當前狀態
輸入
第一個數字m表示有m個操作
后面m行表示m個操作
每行輸入一個數字op
如果op=1表示第一個操作，后面接著兩個數字a,b表示在第a個位置插入b（a以及a后的數字后移）
如果op=2表示第二個操作，后面接著一個數字a表示洗掉第a數字
如果op=3表示第三個操作，查詢當前數列的狀態
（m<=1000，操作保證合法）
輸出
對于每一個op=3輸出當前數列的狀態
樣例輸入
3
1 1 3
1 2 4
3
樣例輸出
3 4
思路
這題本來是作為鏈表題來出的，后面改了資料范圍，那用陣列暴力模擬也可以過
陣列代碼
#include<bits/stdc++.h>
#include<string.h>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int ans[maxn];
int main()
{
int n,op,now=0,a,b;
scanf("%d",&n);
while(n--){
scanf("%d",&op);
if(op==1){
scanf("%d %d",&a,&b);
++now;
for(int i=now;i>a;--i){//插入位置到最后一個元素右移
ans[i]=ans[i-1];
}
ans[a]=b;
}else if(op==2){
scanf("%d",&a);
for(int i=a;i<now;++i){//洗掉位置后一個元素到最后一個元素左移
ans[i]=ans[i+1];
}
--now;
}else{
for(int i=1;i<=now;++i){
printf("%d%c",ans[i],i==now?'\n':' ');
}
}
}
return 0;
}
鏈表代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
struct node{//鏈表節點結構體
int v;
node *nex;
};
void cout_(node *head){//回圈輸出鏈表的值
node *now=head->nex;//第一個元素是head的nex（head是不存東西的）
while(now!=NULL){//回圈輸出，直到鏈表末尾
printf("%d",now->v);
now=now->nex;
if(now!=NULL){
printf(" ");
}
}
printf("\n");
}
int main()
{
int n,m,op,a,b;
node *head=(node*)malloc(sizeof(node));//給頭結點指標分配記憶體
head->nex=NULL;
scanf("%d",&m);
for(int i=1;i<=m;++i){
scanf("%d",&op);
if(op==1){
scanf("%d %d",&a,&b);
a--;
node *now=head;
while(a--){//找到插入位置的前一個元素
now=now->nex;
}
node *ne=(node*)malloc(sizeof(node));
//鏈表插入
ne->v=b;
ne->nex=now->nex;
now->nex=ne;
}else if(op==2){
scanf("%d",&a);
a--;
node *now=head;
while(a--){//找到洗掉位置的前一個元素
now=now->nex;
}
//鏈表洗掉
node *p=now->nex;
now->nex=p->nex;
free(p);
}else{
//輸出鏈表資料
cout_(head);
}
}
return 0;
}
問題 C: 回文素數
題目描述
現有一個正整數，希望去掉這個數中某一個數字之后可以得到一個回文素數，
回文素數是指一個素數同時還是一個回文數（回文數即從左到右和從右到左均一樣的數，例如12321），【注意：一位數也被認為是回文數】
輸入兩個正整數N和M，滿足N<M，請撰寫一個程式統計N和M之間存在多少個滿足上述要求的數？
輸入
單組輸入，輸入一行，包含兩個正整數N和M，1<=N<M<=1000000，兩個數字之間用空格隔開，
輸出
輸出在N和M之間（包含N和M）滿足要求的數的個數，
樣例輸入
110 120
樣例輸出
10
提示
在110和120之間存在10個滿足要求的數，分別是110、111、112、113、114、115、116、117、118和119，它們去掉最后一位數都可以得到一個回文素數11，
思路
暴力列舉區間[n,m]，列舉去掉每一位的數字，判斷回文和素數
下面的代碼用了6素數法（當然普通的也可以）
就是素數都在6的左右兩邊，所以只需要判斷能否被6左右兩邊的數字整除就可以了
證明：
所有的數字可以寫成
6*k+0,6*k+1,6*k+2,6*k+3,6*k+4,6*k+5
這6種形式，+0的可以被6整除，+2，+4的可以被2整除，+3的可以被3整除
那就只剩下+1和+5的
+1的在6的倍數的右邊，+5的也就是-1，在6的倍數的左邊
代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
int get(int x){//獲取數字x的位數
int ans=0;
while(x){
++ans;
x/=10;
}
return ans;
}
int a[105];
bool ju1(int x){//判斷素數
if(x<=3)return x>1;
if(x%2==0||x%3==0)return 0;
int k=sqrt(x)+1;
for(int i=5;i<k;i+=6){
if(x%i==0||x%(i+2)==0)return 0;
}
return 1;
}
bool ju2(int x){//判斷回文
int a=x,b=0;
while(x){
b=b*10+x%10;
x/=10;
}
return (a==b);
}
int ju(int x){//判斷回文素數
int lx=get(x);
for(int i=lx;i>=1;--i){//將x拆分成一位位的存放到陣列a中
a[i]=x%10;
x/=10;
}
for(int i=1;i<=lx;++i){//列舉去掉的位數
int y=0;
for(int j=1;j<=lx;++j){//獲取去掉第i位后的數字
if(j==i)continue;
y=y*10+a[j];
}
if(ju1(y)&&ju2(y)){//判斷素數和回文
return 1;
}
}
return 0;
}
int vis[maxn];
int main()
{
int n,m,ans=0;
scanf("%d %d",&n,&m);
for(int i=n;i<=m;++i){
if(ju(i)){
++ans;
}
}
printf("%d\n",ans);
return 0;
}
問題 D: 數列求和
題目描述
求以下數列的和：
f(n)=1/5-1/10+1/15-1/20+1/25-......+1/(5*(2*n-1))-1/(5*2*n)，
輸入
每組資料一個輸入，每個輸入一行，輸入n，（n<=100）
輸出
輸出數列前n項的和，結果四舍五入保留四位小數，
樣例輸入
1
樣例輸出
0.1000
思路
由最后兩項可以知道，數列是
（1/5-1/10）+（1/15-1/20）+...+（1/(5*(2*n-1))-1/(5*2*n)）
所以直接計算f(n)將中間答案累加就可以了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
int main()
{
int n;
double ans=0,res=0;
scanf("%d",&n);
for(int i=1;i<=n;++i){
ans+=1.0/(5*(2*i-1))-1.0/(5*2*i);
res+=ans;
}
printf("%.4lf\n",res);
return 0;
}
問題 E: 牛牛的鬧鐘
題目描述
牛牛總是睡過頭，所以他定了很多鬧鐘，只有在鬧鐘響的時候他才會醒過來并且決定起不起床，從他起床算起他需要X分鐘到達教室，上課時間為當天的A時B分，請問他最晚可以什么時間起床？
輸入
每個輸入包含一個測驗用例，
每個測驗用例的第一行包含一個正整數，表示鬧鐘的數量N(N<=100)，
接下來的N行每行包含兩個整數，表示這個鬧鐘響起的時間為Hi(0<=A<24)時Mi(0<=B<60)分，
接下來的一行包含一個整數，表示從起床算起他需要X(0<=X<=100)分鐘到達教室，
接下來的一行包含兩個整數，表示上課時間為A(0<=A<24)時B(0<=B<60)分，
資料保證至少有一個鬧鐘可以讓牛牛及時到達教室，
輸出
輸出兩個整數表示牛牛最晚起床時間，
樣例輸入
3
5 0
6 0
7 0
59
6 59
樣例輸出
6 0
思路
回圈判斷最大的小于最遲起床時間的時間
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
struct node{
int a,b;
}w[105];
int main()
{
int n,x,a,b;
while(~scanf("%d",&n)){
for(int i=1;i<=n;++i){
scanf("%d %d",&w[i].a,&w[i].b);
}
scanf("%d %d %d",&x,&a,&b);
int en=a*60+b;//上課時間
int ans=0;
for(int i=1;i<=n;++i){
int st=w[i].a*60+w[i].b+x;//第i個點起到學校的時間
if(st<=en&&st>w[ans].a*60+w[ans].b+x){//可以到學校并且比記錄的答案更優就更新
ans=i;
}
}
printf("%d %d\n",w[ans].a,w[ans].b);
}
return 0;
}
問題 F: 繁殖
題目描述
在R星球有一類昆蟲它是可以無性繁殖的，身為昆蟲調查員的你接到了命令前往R星球去調查昆蟲的繁殖情況
經過一系列的調查，你發現該種昆蟲一生最多可以繁殖出兩個子代，現在你發現了這種昆蟲身上可能會帶有一種病毒，上級已經給你發來通知，告訴你了兩只帶有該病毒昆蟲的編號，
為了快速找出這種病毒你必須找到這兩只昆蟲的最近公共父輩(不會存在兩只昆蟲出現相同編號)，
輸入
第一行 一段序列，代表昆蟲的序號，每個昆蟲帶有兩個子代，若沒有子代的用-1代替，（如序列：1 2 -1 -1 3 -1 -1，表示1號有2，3兩個子代而2，3沒有子代，類似于二叉樹的先序遍歷）
第二行 兩個已知帶有病毒的昆蟲編號
輸出
輸出一行，代表病毒昆蟲的公共父輩編號
樣例輸入
3 5 6 -1 -1 2 7 -1 -1 4 -1 -1 1 9 -1 -1 8 -1 -1
5 1
樣例輸出
3
思路
最近公共祖先問題（LCA）
最樸素的解法是求出每個點的深度，對于要判斷的兩個點，先一次次讓深度深的走向它的父節點，直到兩個點深度一樣，再同時讓它倆走向所在點的父節點，直到走到同一個節點，這個點就是所求兩個點的最近公共祖先
樸素LCA代碼
#include<bits/stdc++.h>
#include<string>
#define ll long long
using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
struct node{
int l,r,v;
};
node edge[maxn];
int cnt=0,pre[maxn],dep[maxn];
int fa[maxn];
int build(int v,int f){
int x,now=++cnt;
scanf("%d",&x);
edge[now].v=x;//第now個節點的昆蟲編號
dep[now]=v;//第now個節點的深度
fa[now]=f;//第now個節點的父節點編號
if(x!=-1){
pre[x]=now;//編號為i的昆蟲對應的節點編號
edge[now].l=build(v+1,now);
edge[now].r=build(v+1,now);
}
}
int lca(int a,int b){
if(dep[a]<dep[b])swap(a,b);//將a換成深的節點
while(dep[a]!=dep[b]){//將a一步步上移
a=fa[a];
}
while(a!=b){//a,b同時上移
a=fa[a];
b=fa[b];
}
return edge[a].v;//回傳a節點的昆蟲編號
}
int main()
{
build(1,0);
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",lca(pre[a],pre[b]));
return 0;
}
容易發現上移程序是一步步的，很憨，那可以考慮多跨幾步嘛
然后就有了LCA的倍增優化，倍增優化是利用二進制的性質
dp[i][j]表示第i個節點上移j次所在的節點
具體實作看代碼吧
倍增優化LCA代碼
#include<bits/stdc++.h>
#include<string>
#define ll long long
using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
struct node{
int l,r,v;
};
node edge[maxn];
int cnt=0,pre[maxn],dep[maxn];
int dp[maxn][32];
int build(int v,int fa){
int x,now=++cnt;
scanf("%d",&x);
edge[now].v=x;
dep[now]=v;
dp[now][0]=fa;
if(x!=-1){
pre[x]=now;//編號為i的昆蟲對應的節點數
edge[now].l=build(v+1,now);
edge[now].r=build(v+1,now);
}
}
int lca(int a,int b){
if(dep[a]<dep[b])swap(a,b);
int x=dep[a]-dep[b];//兩個點的深度距離
for(int i=0;i<=28;++i){//將a和b的深度距離二進制化地對a進行上移
if(x&(1<<i)){
a=dp[a][i];
}
}
if(a==b)return edge[a].v;
for(int i=28;i>=0;--i){
if(dp[a][i]!=dp[b][i]){
a=dp[a][i];
b=dp[b][i];
}
}
return edge[dp[a][0]].v;
}
int main()
{
build(1,0);
for(int i=1;i<=28;++i){
for(int j=1;j<=cnt;++j){
dp[j][i]=dp[dp[j][i-1]][i-1];//處理出所有的dp陣列
}
}
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",lca(pre[a],pre[b]));
return 0;
}
問題 G: 1234
題目描述
小明的弟弟剛剛學會了寫英語的一(one)、二(two)、三(three)和四(four)，
他在紙上寫了一個單詞，這個單詞是one、two、three和four中的某一個，已知單詞最多只有一個字母寫錯，但是單詞的長度肯定不會錯，
你能認出他寫的是哪個單詞嗎？
輸入
單組輸入，
輸入占1行，對應一個單詞，單詞長度正確，且最多只有一個字母寫錯，所有字母都是小寫字母，且輸入保證只有一種理解方式，
輸出
輸出一行，即該單詞對應的阿拉伯數字，
樣例輸入
thref
樣例輸出
3
思路
先判斷長度，如果是長度是5那就是3如果長度是4那就是4
如果長度是3就判斷一下和"one"對應有幾個位上的字符相等，有大于等于2個數字相等就是1，否則是2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
string s;
int main()
{
cin>>s;
if(s.size()==5){
cout<<"3"<<endl;
}else if(s.size()==4){
cout<<"4"<<endl;
}else{
if(((s[0]=='o')+(s[1]=='n')+(s[2]=='e'))>=2){
cout<<"1"<<endl;
}else{
cout<<"2"<<endl;
}
}
return 0;
}
問題 H: 尋找蟲蟲
題目描述
小蟲蟲由于出來找食物飛走了，小紅紅回到學校之后發現蟲蟲不見了，好在他在蟲蟲的身上裝了定位，小紅紅跟著定位來到了一個迷宮，這個迷宮很復雜，幾乎每條道路都是交錯的，為了能快的找到蟲蟲，你能幫助小紅紅判斷該路徑是否存在回路嘛？
Tips：
在離散數學的定義下：在某個集合上的偏序得出全序的程序稱為拓撲排序，
偏序：若集合S上的關系R為自反，反對稱和傳遞的，則稱R是集合S上的偏序關系
設R是集合S上的偏序，若對于每個x，y∈xRy或yRx，則稱R為集合S的全序，
拓撲排序的流程如下：
\1. 在有向圖中選取一個沒有前驅節點的點輸出
\2. 從圖中洗掉該頂點和所有以該點為尾的弧
一直重復以上步驟，直至頂點全部輸出，或圖中存在環為止，
輸入
輸入的第一行包含一個整數n，表示有n個節點，n不超過50
之后的n行中有整數0和1，對于第i行j列的值，若為1則表示i與j兩點有邊連接且又向的i點指向j點，若為0則沒有邊，保證不存在點的自回路（即i == j 時的值為0）
輸出
若讀入的有向圖含有回路，輸入"can not find the bug"
若沒有回路，則按照題目的描述依次輸出圖的拓撲排序后的有序數列，每個整數后輸出一個空格，
注意尾行的換行，
樣例輸入
4
0 1 0 0
0 0 1 0
0 0 0 0
0 0 1 0
樣例輸出
3 0 1 2
思路
按題目要求進行拓撲排序…
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
int w[105][105],in[105],ans[105],cnt;
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
scanf("%d",&w[i][j]);
if(w[i][j]){//計算入度
++in[j];
}
}
}
queue<int> pq;
for(int i=n;i>=1;--i){//由樣例可知是從大到小遍歷
if(in[i]==0){//將入度為0的入隊
pq.push(i);
}
}
while(!pq.empty()){//將隊中的出隊
int now=pq.front();
pq.pop();
ans[++cnt]=now-1;
for(int i=n;i>=1;--i){//由樣例可知是從大到小遍歷
if(w[now][i]){//要出隊的點有邊的入度減一
--in[i];
w[now][i]=0;
if(in[i]==0){//入度減為0就入隊
pq.push(i);
}
}
}
}
if(cnt==n){//如果所有都被遍歷完了說明沒有回路
for(int i=1;i<=cnt;++i){
printf("%d%c",ans[i],i==cnt?'\n':' ');
}
}else{
printf("can not find the bug\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/26455.html
標籤：其他
上一篇：IP