Is It A Tree?

問題

考試時應該做不出來，果斷放棄

樹是一種眾所周知的數據結構，它要么是空的(null, void, nothing)，要么是一個或的集合滿足以下屬性的節點之間有向邊連接的節點較多。
?只有一個節點，稱為根節點，它沒有有向邊指向。
?除了根節點外，每個節點都有一條邊指向它。
?從根到每個節點有一個唯一的有向邊序列。
例如，考慮下面的插圖，其中節點由圓圈和邊表示用帶箭頭的線表示。前兩個是樹，最后一個不是。

在這個問題中，你會得到一些有向連接的節點集合的描述邊緣。對于其中的每一個，您都要確定集合是否滿足樹的定義。
輸入
輸入將由一系列描述(測試用例)和一對負整數組成。每個測試用例將由邊緣描述序列組成，每個邊緣后面跟著一對零描述將由一對整數組成;第一個整數標識該邊從哪個節點出發開始，第二個整數標識該邊所指向的節點。節點號將總是大于0。
輸出
對于每個測試用例，顯示“case k是一個樹”這行。’或者‘Case k不是樹’這條線。”,即K對應于測試用例編號(它們從1開始順序編號)。?

思路

? ? ①先判斷是不是空樹，如果是空樹（直接輸入兩個0），就直接判斷是樹；

? ? ②然后找這棵樹的根節點，如果有一個節點它的入度為0而出度不為0，那它就是根節點，如果沒有找到這樣的結點就判斷它不是樹；

? ? ③在找到一個根節點之后，用廣度優先遍歷的方法，通過根節點遍歷一遍這棵樹，如果兩次遍歷到同一個結點，那就說明這個結點的入度不是1，這就不是樹；

? ? ④廣度優先遍歷結束之后，如果所有的結點都被訪問過了，那就說明這是樹，否則就不是樹（不是連通的）。

代碼?

#include <cstdio>
#include <cstdlib>
#include <climits>
#include <memory>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <iostream>
using namespace std;const int maxn = 10000;int first[maxn];
int second[maxn];
int counter;
bool visited[maxn];queue<int> q;bool isRoot(int index, int counter)
{bool retVal = false;for(int i = 0; i < counter; i++){if(second[i] == index) return false;if(first[i] == index) retVal = true;}return retVal;
}int main()
{int number = 0;int first_in, second_in;while(cin>>first_in>>second_in){if(first_in == -1 || second_in == -1) break;if(first_in == 0 && second_in == 0){printf("Case %d is a tree.\n", ++number);continue;}counter = 0;memset(visited, 0, sizeof(visited));do{if(first_in == 0 && second_in == 0) break;first[counter] = first_in;second[counter] = second_in;++counter;}while(cin>>first_in>>second_in);// find a root nodeint index;for(index = 0; index < maxn; index++){if(isRoot(index, counter)) break;}if(index == maxn){printf("Case %d is not a tree.\n", ++number);continue;}while(!q.empty()) q.pop();q.push(index);bool isTree = true;int treesize = counter;while(!q.empty()){int root = q.front();q.pop();if(visited[root]){isTree = false;break;}visited[root] = true;for(int i = 0; i < counter; i++){if(first[i] == root){q.push(second[i]);--treesize;}}}if(!isTree || treesize != 0)printf("Case %d is not a tree.\n", ++number);elseprintf("Case %d is a tree.\n", ++number);}
}

Global Raining at Bididibus

問題

好難呀

?

思路

(⊙o⊙)…這道題網絡上居然沒有找到解題方法

代碼?

在CSDN上看到唯一提到這道題的點進去發現居然是我自己

---

【碎碎念】

我終于知道為什么往屆同學做這套題的很少，原來是因為太難了QAQ

這套題第一道題和第三道題可以嘗試去做，第二套爭取會做

---

Tokitsukaze and All Zero Sequence

代碼?

#include<stdio.h>
int main(){int t;scanf("%d",&t);for(int i=0;i<t;i++){int flag=0;//注意初始化 int ch;int n;int a[101]={0};scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&ch);a[ch]++;if(a[ch]>1)//注意是大于1 flag=1;}if(a[0]>0)	printf("%d\n",n-a[0]);else {if(flag==1)printf("%d\n",n);//輸出0和1時不要弄混 if(flag==0)printf("%d\n",n+1);}}return 0;
}

Aggressive cows?

代碼

#include<iostream> 
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,c;
int a[100005];bool fun(int m){int cnt=1,cur=0,next=1;while(next<n){next++;if(a[next]-a[cur]>=m){cnt++;cur=next;}}if(cnt>=c) return true;else return false;
}
int main(){scanf("%d %d",&n,&c);for(int i=0;i<n;i++){scanf("%d",&a[i]);}int l=a[0],r=a[n-1];int ans=0;sort(a,a+n);while(l<=r){int mid=(l+r)/2;if(fun(mid)){ans=mid;l+mid+1;}else{r=mid-1;}}printf("%d",ans);return 0;
}

Brainman

代碼

#include<iostream> 
#include<stdio.h> 
using namespace std;const int n=200000;
int a[n];//一個N個數的序列int main(){int m;scanf("%d",&m);//場景的數量 for(int k=1;k<=m;k++) {int p;sccanf("%d",&p);//長度 for(int i=1;i<=p;i++)scanf("%d",&a[i]) ;//元素 int cnt=0;for(int i=1;i<=p;i++){for(int j=i+1;j<=p;j++){if(a[i]>a[j])//交換位置 cnt++;}}printf("Scenario #%d:\n%d\n\n",k,cnt);}return 0;
}

Tokitsukaze and Good 01-String (hard version)

?代碼

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>using namespace std;
typedef long long ll;const int N = 2e5 + 10;
int n;
string s;int main()
{int T;cin >> T;while(T--){cin >> n >> s;int x = 0, y = 0;char last = ' ';for (int i = 0; i < s.size(); i += 2){if (s[i] != s[i+1])x++;else{if (last != s[i])y++;last = s[i];}}printf("%d %d\n", x, (y > 1) ? y : 1);}return 0;
}

學習規劃

?