連結：戳這裡
C. Bear and Forgotten Tree 3 time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output A tree is a connected undirected graph consisting of n vertices and n - 1 edges. Vertices are numbered 1 through n.
Limak is a little polar bear and Radewoosh is his evil enemy. Limak once had a tree but Radewoosh stolen it. Bear is very sad now because he doesn't remember much about the tree — he can tell you only three values n, d and h:
The tree had exactly n vertices.
The tree had diameter d. In other words, d was the biggest distance between two vertices.
Limak also remembers that he once rooted the tree in vertex 1 and after that its height was h. In other words, h was the biggest distance between vertex 1 and some other vertex.
The distance between two vertices of the tree is the number of edges on the simple path between them.
Help Limak to restore his tree. Check whether there exists a tree satisfying the given conditions. Find any such tree and print its edges in any order. It's also possible that Limak made a mistake and there is no suitable tree – in this case print "-1".
Input
The first line contains three integers n, d and h (2 ≤ n ≤ 100 000, 1 ≤ h ≤ d ≤ n - 1) — the number of vertices, diameter, and height after rooting in vertex 1, respectively.
Output
If there is no tree matching what Limak remembers, print the only line with "-1" (without the quotes).
Otherwise, describe any tree matching Limak's description. Print n - 1 lines, each with two space-separated integers – indices of vertices connected by an edge. If there are many valid trees, print any of them. You can print edges in any order.
Examples
input
5 3 2
output
1 2
1 3
3 4
3 5
input
8 5 2
output
-1
input
8 4 2
output
4 8
5 7
2 3
8 1
2 1
5 6
1 5
Note
Below you can see trees printed to the output in the first sample and the third sample.
題意：給出一棵樹,n個節點,直徑為d,深度為h,要求畫出滿足條件的樹即可,根節點必須為1
輸出的話直接輸出邊就可以了
思路：首先如果樹的深度*2都不能>=直徑的話肯定是-1,還有就是n>=3的時候直徑還小于2就構造不出來了,直徑至少是2吧 是以這也是-1的情況
然後,樹的根節點必須是1,樹的直徑必須是d,通過深度可以先填好直徑,然後所有剩下來的點肯定都連1啊
但是會有問題,那就是至少連根節點1的情況下直徑又+1,這個時候需要判斷的就是目前的直徑是否為0了
還有一種做法就是把樹的直徑按深度填好,然後直接無腦在2上連沒有連的節點
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define maxn 0x3f3f3f3f
#define MAX 1000100
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef unsigned long long ull;
#define INF (1ll<<60)-1
using namespace std;
int n,d,h;
int main(){
scanf("%d%d%d",&n,&d,&h);
if(h*2<d || (n>2 && d<2) ){
cout<<-1<<endl;
return 0;
}
int t=h,i=2;
while(t--){
cout<<i-1<<" "<<i<<endl;
i++;
d--;
}
int j=1;
if(d==0){
while(i!=n+1) {
cout<<2<<" "<<i<<endl;
i++;
}
}else {
while(d--){
cout<<j<<" "<<i<<endl;
j=i;
i++;
}
while(i!=n+1) {
cout<<1<<" "<<i<<endl;
i++;
}
}
return 0;
}
D. Bear and Polynomials time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Limak is a little polar bear. He doesn't have many toys and thus he often plays with polynomials.
He considers a polynomial valid if its degree is n and its coefficients are integers not exceeding k by the absolute value. More formally:
Let a0, a1, ..., an denote the coefficients, so
. Then, a polynomial P(x) is valid if all the following conditions are satisfied:
1：ai is integer for every i;
2：|ai| ≤ k for every i;
3：an ≠ 0.
Limak has recently got a valid polynomial P with coefficients a0, a1, a2, ..., an. He noticed that P(2) ≠ 0 and he wants to change it. He is going to change one coefficient to get a valid polynomial Q of degree n that Q(2) = 0. Count the number of ways to do so. You should count two ways as a distinct if coefficients of target polynoms differ.
Input
The first line contains two integers n and k (1 ≤ n ≤ 200 000, 1 ≤ k ≤ 109) — the degree of the polynomial and the limit for absolute values of coefficients.
The second line contains n + 1 integers a0, a1, ..., an (|ai| ≤ k, an ≠ 0) — describing a valid polynomial
. It's guaranteed that P(2) ≠ 0.
Output
Print the number of ways to change one coefficient to get a valid polynomial Q that Q(2) = 0.
Examples
input
3 1000000000
10 -9 -3 5
output
3
input
3 12
10 -9 -3 5
output
2
input
2 20
14 -7 19
output
Note
In the first sample, we are given a polynomial P(x) = 10 - 9x - 3x2 + 5x3.
Limak can change one coefficient in three ways:
He can set a0 = - 10. Then he would get Q(x) = - 10 - 9x - 3x^2 + 5x^3 and indeed Q(2) = - 10 - 18 - 12 + 40 = 0.
Or he can set a2 = - 8. Then Q(x) = 10 - 9x - 8x^2 + 5x^3 and indeed Q(2) = 10 - 18 - 32 + 40 = 0.
Or he can set a1 = - 19. Then Q(x) = 10 - 19x - 3x^2 + 5x^3 and indeed Q(2) = 10 - 38 - 12 + 40 = 0.
In the second sample, we are given the same polynomial. This time though, k is equal to 12 instead of 109. Two first of ways listed above are still valid but in the third way we would get |a1| > k what is not allowed. Thus, the answer is 2 this time.
題意：給出一個多項式Ｆ(x)=a0*x^1+a1*x^2+...+an*x^n 當x==2時 F(2)!=0 需要改變當且僅當一個系數ai的值使得Q(2)=0。
并且這個更改後的系數的絕對值不能超過k 且an!=0
思路：首先我們把它換位思考一下,當x=10的時候,我來描述一組樣例
n=3 k=1e9
10 -9 -3 5
F(10)=10-9*10^1-3*10^2+5*10^3
我們要改變一個系數的值使得整個Q(10)=0 ,分析一下,如果在個位上的值是3的話,那麼不管我怎麼去改十位百位千位的值都無法使Q(10)=0,因為十位百位千位都無法變成3,都至少是10的倍數,那麼問題就出現了,這個情況下我們隻能通過改個位上的值去滿足十位百位千位使得Q(10)=0.
下面我們回到原題,當x=2的時候,我們想象成二進制的數
n=3 k=1e9
10 -9 -3 5
F(2)=10-9*2^1-3*2^2+5*2^3
參照x=10的情況,當低位上存在值得時候,是無法通過更改高位的值使得Q(2)=0的。
是以我們隻能更改低位上的值且目前低位上的系數為0的時候,才能使Q(2)=0.
是以我們把系數ai也換成二進制,然後問題也就差不多可以解決了
還需要注意的地方就是要先找出第一個ai不為0的位置,是以目前位置之前的所有位置上的系數都是0,這些位置都可以更改系數值
還需要注意的就是更改的值得範圍不能超出k,基本上這道題就過了
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define MAX 1000100
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef unsigned long long ull;
#define INF (1ll<<60)-1
using namespace std;
int n,k;
int a[1000100],b[1000100];
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<=n;i++) {
scanf("%d",&a[i]);
b[i]=a[i];
}
for(int i=0;i<n;i++){
a[i+1]+=a[i]/2;
a[i]%=2;
}
int t=0;
for(int i=0;i<=n;i++){
if(a[i]==0) continue;
t=i;
break;
}
ll ans=0;
int num=0;
for(int i=n;i>=0;i--){
ans=ans*2+(ll)a[i];
if(abs(ans)>=1LL*1e9*1e9) break;
if(i<=t){
if(abs(ans-(ll)b[i])>k) continue;
if(i==n && abs(ans-(ll)b[i])==0) continue;
num++;
}
}
cout<<num<<endl;
return 0;
}<strong>
</strong>