A-欧几里得

题目描述

欧几里得算法是一种求最大公约数的有效算法，在算法竞赛中很常用。
Python代码实现如下：

1
2
3
4
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

现在，如果已知 gcd(a,b) 共递归了 n次，求所有可能的a,b中满足a>b>=0且a+b最小的一组的a与b之和。

输入描述

第一行一个整数,T。
接下来T行一行一个整数，n。

输出描述

T行，每行一个整数，代表a+b。

示例1

输入
1
0
输出
1
说明
gcd(1,0) 由于 b=0，不会递归，即是递归0次。

示例2

输入
1
1
输出
3
说明
gcd(2,1)会递归一次至gcd(1,0)。

思路

题给的两个样例非常具有启发性。(2,1)递归一次变为(1,0)。那么我们给出的(a,b)最终必定会递归至(2,1)–>(1,0)。(a,b)一步递归后变为(b,a%b)，这是一定的；但是从(b,a%b)反推(a,b)有多种情况，而使a+b最小的情况是(a,b)=(b+a%b,b)。于是有序列(1,0),(2,1),(3,2)。求这个序列我们可以直接递推，也可以用斐波那契数列递推。能够产生这样的递推方式，是因为此题满足“最优子结构”“无后效性”“重复子问题”，此题本质上是动态规划。

代码1

直接递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node
{
	long long a;
	long long b;
}p[100];
int main()
{
	p[0].a=1;
	int i;
	p[0].b=0;
	p[1].a=2;
	p[1].b=1;
	for(i=2;i<=90;i++)
	{
		p[i].b=p[i-1].a;
		p[i].a=p[i-1].a+p[i-1].b;
	}
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int k;
		scanf("%d",&k);
		printf("%lld\n",p[k].a+p[k].b);
	}
	return 0;
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
typedef long long ll;
ll fib[110]={0}; 
int main() 
{
    fib[0]=1;
    fib[1]=2;
    int i;
    for(i=2;i<=100;i++) fib[i]=fib[i-1]+fib[i-2];
    int T,n;
    cin>>T;
    while(T--)
    {
        cin>>n;
        if(n==0)cout<<1<<endl;
        else cout<<fib[n]+fib[n-1]<<endl;
    }
    return 0;
}

B-括号序列

题目描述

给出一个仅包含’[‘,’]‘,’(‘,’)‘,’{‘,’}'六种字符的括号序列，判断其是否合法。
空串是一个合法的括号序列。
如果A, B 都是合法的括号序列，那么AB也是合法的括号序列。
如果A是合法的括号序列，(A) , [A], {A}都是合法的括号序列。

输入描述

一行一个字符串S，只包含题目中的六种括号字符。

输出描述

输出为一行"Yes" 或"No"。

示例1

输入
(){}[]
输出
Yes

示例2

输入
({[]})
输出
Yes

示例3

输入
([)]
输出
No

备注

1≤∣S∣≤1000000

思路

这是一个配对问题。不合法有两种情况，一种是左右括号数量不一致，另一种是左右括号种类不一致。运用简单的数据结构：栈。非常坑的是用STL会导致堆栈溢出，于是手写了一个。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<string>
using namespace std;
char stack[1000005];
int main()
{
    string s;
    cin>>s;
    bool flag=1;
    int i;
    int head=0;
    for(i=0;i<s.length();i++)
    {
        if(s[i]=='(') stack[++head]=s[i];
        else if(s[i]==')')
        {
            if(stack[head]!='(')
            {
                flag=0;
                break;
            }
            else head--;
        }
        else if(s[i]=='[') stack[++head]=s[i];
        else if(s[i]==']')
        {
            if(stack[head]!='[')
            {
                flag=0;
                break;
            }
            else head--;
        }
        else if(s[i]=='{') stack[++head]=s[i];
        else if(s[i]=='}')
        {
            if(stack[head]!='{') 
            {
                flag=0;
                break;
            }
            else head--;
        }
    }
    if(!flag||head) cout<<"No";//栈非空（左右括号数量不一致）或者左右括号种类不一样
    else cout<<"Yes";
    return 0;
}

C-子段乘积

题目描述

给出一个长度为 nn 的数列 a1,a2,...,ana_1,a_2,...,a_n，求其长度为 k 的连续子段的乘积对 998244353 取模余数的最大值。

输入描述

第一行两个整数n,k。
第二行n个整数,a1,a2,…,an。

输出描述

输出一个整数，代表最大余数。

示例1

输入
5 3
1 2 3 0 8
输出
6
说明
1∗2∗3mod998244353=6

备注

1≤k≤n≤2∗10⁵
0≤ai<998244353

思路

用尺取法，前缀和之类的，似乎都要注意串中存在0的情况，但是我又不知道有0怎么处理。于是就规避这件事，用线段树维护区间内所有数的乘积。
我们只要枚举所有长度为k的区间，找出最大值即可。此题只有查询操作，没有更新操作，用线段树显得异常简单，可以视作一道线段树的板子题。然而比赛的时候wa了8次，赛后才发现错误。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstdio>
#define N 200002
#define ll long long
using namespace std;
const ll mod=998244353;
struct Segment
{
    int l,r;
    ll v;
}tree[N<<2];
ll a[N];
void build(int id,int l,int r)
{
    tree[id].l=l;
    tree[id].r=r;
    if(l==r)
    {
        tree[id].v=a[l]%mod;
        return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    tree[id].v=tree[id<<1].v*tree[id<<1|1].v%mod;
}
ll query(int id,int l,int r)
{
    if(l<=tree[id].l&&tree[id].r<=r)
    {
        return tree[id].v%mod;
    }
    ll res=1;
    int mid=(tree[id].l+tree[id].r)>>1;
    if(l<=mid) res=res*query(id<<1,l,r)%mod;
    if(r>=mid+1) res=res*query(id<<1|1,l,r)%mod;
    return res;
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int i;
    for(i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    ll ans=0;
    for(i=1;i<=n-k+1;i++)
    {
        ans=max(ans,query(1,i,i+k-1)%mod);
    }
    printf("%lld",ans%mod);
    return 0;
}

D-子段异或

题目描述

输入一个数列a，你需要输出其中异或值为0的不同子段的数量。一个子段 [l,r] (1≤l≤r≤n)的异或值为a[l]⊕a
[l+1]⊕a[l+2]⊕…⊕a [r]，其中⊕符号代表异或运算。
两个子段被视为相同的，当且仅当其开始和结束位置均对应相同。

输入描述

第一行一个整数n，代表数列长度。
第二行n个整数，代表数列。

输出描述

输出一个整数，代表答案。

示例1

输入
5
1 2 3 2 1
输出
2
说明
子段 [1,3] 和子段 [3,5] 是合法子段。

备注

$n≤200000,0≤ai≤{2^{30}}-1$

思路

定义前缀异或和prefix[]。区间[l,r]的异或和为0，说明prefix[l-1]^prefix[r]=0，即prefix[l-1]=prefix[r]。
由于异或数据可能很大，我们用map<long long,int>cnt进行离散化操作，记录每一个异或前缀和的值出现的次数。假设某一个异或值出现了n次，我们要从其中选出两个值组合，组合数为$C_n^2 = \frac{{n(n - 1)}}{2}$，这显然对应这一个和Sn=0+1+2+⋯+(n−1){S_n} = 0 + 1 + 2 + \cdots + (n - 1)。于是我们只要每找到一个值prefix，ans需要加上(cnt[prefix] - 1)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
int main()
{
	ios::sync_with_stdio(false);
	int n;
	ll prefix=0;
	cin>>n;
	map<ll,int>cnt;
	int i;
	ll t;
	ll ans=0;
    cnt[0]=1;//调试一下就知道cnt[0]初值必须设置为1，因为第一位的前缀异或就是0。
	for(i=1;i<=n;i++)
	{
		cin>>t;
		prefix^=t;
        cnt[prefix]++;
		ans=ans+cnt[prefix]-1;		
	}
	cout<<ans;
	return 0;
}

E-最小表达式

题目描述

给出一个包含数字1-9和加号的字符串，请你将字符串中的字符任意排列，但每种字符数目不变，使得结果是一个合法的表达式，而且表达式的值最小。输出那个最小表达式的值
合法的表达式的定义如下：
一个数字，如233，是一个合法的表达式
A + B是合法的表达式，当且仅当 A , B 都是合法的表达式
保证给出的表达式经过重排，存在一个合法的解。

输入描述

一行输入一个字符串，仅包含数字1-9和加号+。
字符串的长度小于5×1055 \times {10^5}。

输出描述

一行输出一个数字，代表最小的解。

示例1

输入
111+1
输出
22
说明
11+11=22

示例2

输入
9998765432111
输出
1112345678999

示例3

输入
12+35
输出
38
说明
25+13=38

示例4

输入
23984692+238752+2+34+
输出
5461
说明
嗯，这个答案是可以得到的

备注

注意，答案长度可能长达500000个字符。

思路

首先，我们要读取字符串，统计加号的个数plus，因为字符是随意组合的，所以我们不妨将字符从小到大排序，这时候加号会排在最前面。
从小到大排序是一种贪心的策略，有plus个加号，我们就需要把字符串分成group=(plus+1)份，要做到每一份数字的个数都较为均匀，且最高位要尽可能小。
于是我们只要将字符从大到小排序，枚举group个数字的最高位，每一次枚举最高位，都需要隔group个字符选取该数字的每一位。
因为数字很庞大，在此抄一下BigInteger的板子。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
#include <iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
struct BigInteger
{
    static const int BASE=100000000; //和WIDTH保持一致
    static const int WIDTH=8;//八位一存储,如修改记得修改输出中的%08d
    bool sign;//符号, 0表示负数
    size_t length;//位数
    vector<int> num;//反序存
    //构造函数
    BigInteger(long long x=0) 
	{ 
		*this=x;
	}
    BigInteger(const string &x) 
	{
	 	*this=x; 
	}
    BigInteger(const BigInteger &x) 
	{ 
		*this=x; 
	}
    //剪掉前导0，并且求一下数的位数
    void cutLeadingZero()
    {
        while(num.back()==0&&num.size()!=1)
        {
            num.pop_back();
        }
        int tmp=num.back();
        if(tmp==0) length=1;
        else
        {
            length=(num.size()-1)*WIDTH;
            while(tmp>0)
            {
                length++;
                tmp/=10;
            }
        }
    }
    //赋值运算符
    BigInteger &operator=(long long x)
    {
        num.clear();
        if(x>=0) sign=true;
        else
        {
            sign=false;
            x=-x;
        }
        do
        {
            num.push_back(x%BASE);
            x/=BASE;
        }while(x>0);
        cutLeadingZero();
        return *this;
    }
    BigInteger &operator=(const string &str)
    {
        num.clear();
        sign=(str[0]!='-'); //设置符号
        int x,len=(str.size()-1-(!sign))/WIDTH+1;
        for(int i=0;i<len;i++)
        {
            int End=str.size()-i*WIDTH;
            int start=max((int)(!sign),End-WIDTH); //防止越界
            sscanf(str.substr(start,End-start).c_str(),"%d",&x);
            num.push_back(x);
        }
        cutLeadingZero();
        return *this;
    }
    BigInteger &operator=(const BigInteger &tmp)
    {
        num=tmp.num;
        sign=tmp.sign;
        length=tmp.length;
        return *this;
    }
    //绝对值
    BigInteger abs() const
    {
        BigInteger ans(*this);
        ans.sign=true;
        return ans;
    }
    //正号
    const BigInteger &operator+() const 
	{
	 	return *this; 	
	}
    //负号
    BigInteger operator-() const
    {
        BigInteger ans(*this);
        if (ans!=0) ans.sign=!ans.sign;           
        return ans;
    }
    // + 运算符
    BigInteger operator+(const BigInteger &b) const
    {
        if(!b.sign)
        {
            return *this-(-b);
        }
        if(!sign)
        {
            return b-(-*this);
        }
        BigInteger ans;
        ans.num.clear();
        for(int i=0,g=0;;i++)
        {
            if(g==0&&i>=num.size()&&i>=b.num.size()) break;              
            int x=g;
            if(i<num.size()) x+=num[i];               
            if(i<b.num.size()) x+=b.num[i];               
            ans.num.push_back(x%BASE);
            g=x/BASE;
        }
        ans.cutLeadingZero();
        return ans;
    }
    // - 运算符
    BigInteger operator-(const BigInteger &b) const
    {
        if(!b.sign)
        {
            return *this+(-b);
        }
        if(!sign)
        {
            return -((-*this)+b);
        }
        if(*this<b)
        {
            return -(b-*this);
        }
        BigInteger ans;
        ans.num.clear();
        for(int i=0,g=0;;i++)
        {
            if (g==0&&i>=num.size()&&i>=b.num.size()) break;             
            int x=g;
            g=0;
            if(i<num.size())
                x+=num[i];
            if(i<b.num.size())
                x-=b.num[i];
            if (x<0)
            {
                x+=BASE;
                g=-1;
            }
            ans.num.push_back(x);
        }
        ans.cutLeadingZero();
        return ans;
    }
    // * 运算符
    BigInteger operator*(const BigInteger &b) const
    {
        int lena=num.size(),lenb=b.num.size();
        BigInteger ans;
        for(int i=0;i<lena+lenb;i++) ans.num.push_back(0);          
        for (int i=0,g=0;i<lena;i++)
        {
            g=0;
            for (int j=0;j<lenb;j++)
            {
                long long x=ans.num[i+j];
                x+=(long long)num[i]*(long long)b.num[j];
                ans.num[i+j]=x%BASE;
                g=x/BASE;
                ans.num[i+j+1]+=g;
            }
        }
        ans.cutLeadingZero();
        ans.sign=(ans.length==1&&ans.num[0]==0)||(sign==b.sign);
        return ans;
    }
    //*10^n 大数除大数中用到
    BigInteger e(size_t n) const
    {
        int tmp=n%WIDTH;
        BigInteger ans;
        ans.length=n+1;
        n/=WIDTH;
        while(ans.num.size()<=n) ans.num.push_back(0);           
        ans.num[n]=1;
        while(tmp--) ans.num[n]*=10;           
        return ans*(*this);
    }
    // /运算符 (大数除大数)
    BigInteger operator/(const BigInteger &b) const
    {
        BigInteger aa((*this).abs());
        BigInteger bb(b.abs());
        if (aa<bb) return 0;            
        char *str=new char[aa.length+1];
        memset(str,0,sizeof(char)*(aa.length+1));
        BigInteger tmp;
        int lena=aa.length,lenb=bb.length;
        for (int i=0;i<= lena-lenb;i++)
        {
            tmp=bb.e(lena-lenb-i);
            while(aa>=tmp)
            {
                str[i]++;
                aa=aa-tmp;
            }
            str[i]+='0';
        }
        BigInteger ans(str);
        delete[] str;
        ans.sign=(ans==0||sign==b.sign);
        return ans;
    }
    // %运算符
    BigInteger operator%(const BigInteger &b) const
    {
        return *this-*this/b*b;
    }
    // ++ 运算符
    BigInteger &operator++()
    {
        *this=*this+1;
        return *this;
    }
    // -- 运算符
    BigInteger &operator--()
    {
        *this=*this-1;
        return *this;
    }
    // += 运算符
    BigInteger &operator+=(const BigInteger &b)
    {
        *this=*this+b;
        return *this;
    }
    // -= 运算符
    BigInteger &operator-=(const BigInteger &b)
    {
        *this=*this-b;
        return *this;
    }
    // *=运算符
    BigInteger &operator*=(const BigInteger &b)
    {
        *this=*this*b;
        return *this;
    }
    // /= 运算符
    BigInteger &operator/=(const BigInteger &b)
    {
        *this=*this/b;
        return *this;
    }
    // %=运算符
    BigInteger &operator%=(const BigInteger &b)
    {
        *this=*this % b;
        return *this;
    }
    // < 运算符
    bool operator<(const BigInteger &b) const
    {
        if(sign!=b.sign) //正负，负正
        {
            return !sign;
        }
        else if(!sign&&!b.sign) //负负
        {
            return -b<-*this;
        }
        //正正
        if (num.size()!=b.num.size())
            return num.size()<b.num.size();
        for (int i=num.size()-1;i>=0;i--)
        {
        	if (num[i]!=b.num[i]) return num[i]<b.num[i];               
		}           
        return false;
    }
    bool operator>(const BigInteger &b) const 
	{
	 	return b<*this;
	}                     // >  运算符
    bool operator<=(const BigInteger &b) const 
	{ 
		return !(b<*this); 
	}                 // <= 运算符
    bool operator>=(const BigInteger &b) const 
	{ 
		return !(*this<b); 
	}                 // >= 运算符
    bool operator!=(const BigInteger &b) const 
	{
	 	return b<*this||*this<b; 
	}       // != 运算符
    bool operator==(const BigInteger &b) const 
	{
		 return !(b<*this)&&!(*this<b); 
	} //==运算符
    // 逻辑运算符
    bool operator||(const BigInteger &b) const 
	{
	 	return *this!=0||b!=0;
	} // || 运算符
    bool operator&&(const BigInteger &b) const 
	{
	 	return *this!=0&&b!=0; 
	} // && 运算符
    bool operator!() 
	{
	 	return (bool)(*this==0); 
	}// ！ 运算符 
    //重载<<使得可以直接输出大数
    friend ostream &operator<<(ostream &out,const BigInteger &x)
    {
        if (!x.sign) out<<'-';           
        out<<x.num.back();
        for (int i=x.num.size()-2;i>=0;i--)
        {
            char buf[10];
            //如WIDTH和BASR有变化,此处要修改为%0(WIDTH)d
            sprintf(buf,"%08d",x.num[i]);
            for (int j=0;j<strlen(buf);j++) out<<buf[j];               
        }
        return out;
    }
    //重载>>使得可以直接输入大数
    friend istream &operator>>(istream &in,BigInteger &x)
    {
        string str;
        in>>str;
        size_t len=str.size();
        int start=0;
        if (str[0]=='-') start=1;           
        if (str[start]=='\0') return in;           
        for (int i=start;i<len;i++)
        {
            if (str[i]<'0'||str[i]>'9') return in;                
        }
        x.sign=!start;
        x=str.c_str();
        return in;
    }
};
int main()
{
	ios::sync_with_stdio(0);
	string s;
	cin>>s;
	sort(s.begin(),s.end());
	int len=s.length();
	int plus=0;//加号的个数
	int i; 
	for(i=0;i<len;i++) 
	{
		if(s[i]=='+') plus++;
	}
	int group=plus+1;
	string temp;
	BigInteger ans=0;
	int j,step;
	for(i=group-1,step=1;step<=group;i++,step++)//枚举group个数字开头
	{
		temp="";
		for(j=i;j<len;j+=group) temp+=s[j];//把以s[i]开头的数字组合
		ans+=BigInteger(temp);
	}
	cout<<ans;
	return 0;
}

F-树上博弈

题目描述

现有一个 n 个点，n-1条边组成的树，其中 1 号点为根节点。
牛牛和牛妹在树上玩游戏，他们在游戏开始时分别在树上两个不同的节点上。
在游戏的每一轮，牛牛先走一步，而后牛妹走一步。他们只能走到没有人的空节点上。如果谁移动不了，就输掉了游戏。现在牛牛和牛妹决定随机选择他们分别的起点，于是他们想知道，有多少种游戏开始的方式，使得牛牛存在一种一定获胜的最优策略。
两种开始方式相同，当且仅当在两种开始方式中牛牛，牛妹的开始位置是分别相同的，否则开始方式就被视作不同的。

输入描述

第一行输入为一个整数 n，代表树的点数。
第二行n-1个整数p2,p3,...,pn{p_2},{p_3},...,{p_n}，分别代表2,3,…,n号点的父节点编号。

输出描述

一行一个整数，代表答案。

示例1

输入
3
1 2
输出
2
说明
当且仅当牛牛在1号点，牛妹在3号点，或者牛牛在3号点，牛妹在1号点时，牛牛才获胜。

示例2

输入
2
1
输出
0
说明
由于无论如何牛牛都无路可走，因此必然牛妹获胜。

示例3

输入
30
1 1 2 1 2 1 3 2 3 4 2 3 1 2 3 4 2 4 5 6 3 4 12 12 12 13 13 13 13
输出
428
说明
QwQ

备注

n⩽106,1⩽pi⩽in \leqslant {10^6},1 \leqslant {p_i} \leqslant i.

思路

首先，注意到输掉的唯一方法是自己的唯一一条边有另一个人，那么自己一定是在叶子上。
令两个人之间的距离为D。每人行动后D增加1或减少1。 因此，每有人走一步D的奇偶性都会改变。
假设最初，在牛牛移动之前，D是偶数。那么当牛牛移动时D将始终为偶数，而当牛妹移动时D将始终为奇数。
请注意，只要牛牛和牛妹的令牌位于相邻的节点中，D=1。因此，如果D为偶数，则他们不在相邻的单元格中，并且牛牛始终可以移动。
另一方面，由于牛牛总是可以移动，因此他可以向牛妹的方向移动，将牛妹必然会最终移动到叶子上。同样，如果最初D是奇数，则牛妹获胜。
因此，答案取决于距离的奇偶性：如果是偶数，则牛牛获胜，否则牛妹获胜。
可以发现，只有牛牛的初始位置和牛妹的初始位置距离为偶数时，牛牛获胜。只需要分别求出深度为奇数的点和深度为偶数的点的数量即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int n;
int depth[1000001];
int main()
{
    ios::sync_with_stdio(false);
    int i;
    cin>>n;
    int father;
    long odd=0,even=0;
    for(i=2;i<=n;i++)
    {
        cin>>father;
        depth[i]=depth[father]+1;
        if(depth[i]&1) odd++;
        else even++;
    }
    even++;//把根节点算上
    cout<<odd*(odd-1)+even*(even-1);
    return 0;
}

G-音乐鉴赏

题目描述

作为“音乐鉴赏”课的任课老师，你的课程作为刷学分好课一直受到广泛欢迎。但这一学期，学校制定了新的标准，你的课的优秀率（分数超过90分的人数）被限制在10%以下！
为了应对这个调整，你要求所有的同学都写了一篇论文，并使用随机算法打出了0-90之间的分数，分数可能不是整数。这里的随机是指，对于在[0,90]这个闭区间上的任何一对等长的区间，分数出现在其中的概率均是相同的。在期末的分数占比为百分之多少的时候，你的课程优秀率期望恰好在10%？保证所有同学的平时成绩都高于90分。

输入描述

输入第一行包含一个整数 n，保证n是10的倍数。
第二行包含 n 个整数，代表同学们的平时成绩。

输出描述

输出一行一个百分数，代表期末分数占比多少为合适。保留两位小数。

示例1

输入
10
99 99 99 99 99 99 99 99 99 99
输出
50.00%
说明
需要随机占比50%。

思路

设某一个人的平时成绩为a,期末随机成绩为b,x为期末成绩占比 (a⩾90,0⩽b⩽90,0⩽x⩽1)(a \geqslant 90,0 \leqslant b \leqslant 90,0 \leqslant x \leqslant 1)。
假设有一条线段，端点为(0,90)，b的取值占线段的全部长度 L=90L = 90 。
如果这个人的总成绩为优秀，那么有a(1−x)+bx⩾90a(1 - x) + bx \geqslant 90，解得$b \geqslant \frac{{90 - (1 - x)a}}{x}$。
此时b占线段长度 $l = 90 - \frac{{90 - (1 - x)a}}{x} = \frac{{(a - 90)(1 - x)}}{x}$。
所以一个人得到优秀的概率为$P = \frac{l}{L} = \frac{{(a - 90)(1 - x)}}{{90x}}$。
这是典型的几何概型。
可以这样理解，每有1个人，就会有P人得到优秀，每个人得到优秀的概率相加就是0.1×n0.1 \times n。
于是得到方程：

$\sum\limits_{i = 1}^n {\frac{{({a_i} - 90)(1 - x)}}{{90x}}} = \frac{n}{{10}}$

解得： $x = \frac{{\sum\limits_{i = 1}^n {({a_i} - 90)} }}{{9n + \sum\limits_{i = 1}^n {({a_i} - 90)} }}$
接下来的事情就很好办了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int sum=0;
    int T=n;
    int a;
    while(T--)
    {
        cin>>a;
        a-=90;
        sum+=a;
    }
    double ans=(1.0*sum)/(9*n+sum)*100;
    printf("%.2lf",ans);
    putchar('%');
    return 0;
}

H-坐火车

题目描述

牛牛是一名喜欢旅游的同学，在来到渡渡鸟王国时，坐上了颜色多样的火车。
牛牛同学在车上，车上有n个车厢，每一个车厢有一种颜色。
他想知道对于每一个正整数x∈[1,n]x∈[1, n]，集合$\{ (i,x,j)|i < x < j,{l_x} \leqslant co{l_i} \leqslant {r_x}\}$中包含多少个元素。
换句话说，就是要求每一个车厢两边有多少对颜色相同的车厢，并且这一对车厢的颜色要在 lxl_x到rxr_x之间。其中colicol_i代表ii号车厢的颜色，lx,rxlx,r_x代表颜色的限制。

输入描述

第一行一个正整数n。
第二行n个三元组，每个三元组包括三个正整数$ (col_i, l_i, r_i)$，输入中没有括号，这 3n 个正整数之间均只用空格隔开，详见样例。

输出描述

输出一行 n 个非负整数代表答案。

示例1

输入
5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
输出
0 3 4 3 0

备注

1≤n≤5⋅1051≤n≤5⋅10^5
1≤coli, li, ri≤5⋅1051 \le col_i,\ l_i,\ r_i \le 5 \cdot 10^5

思路

从左向右遍历，使用树状数组维护每种颜色的该车厢左右的对数即可。
如下一个颜色是colicol_i，应当先减去下一个颜色作为右边的匹配数，再加上当前颜色作为左边的匹配数，注意不要爆long long。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=500009;
struct node
{
	ll l,r;
	ll col;
}cabin[N];
ll suffix[N],prefix[N],ans[N];
ll lowbit(ll x)
{
	return x&(-x);
}
ll n;
void update(ll i,ll val)
{
	while(i<=n)
	{
		ans[i]+=val;
		i+=lowbit(i);
	}
}
ll query(ll i)
{
	ll res=0;
	while(i>0)
	{
		res+=ans[i];
		i-=lowbit(i);
	}
	return res;
}
void solve()
{
	cin>>n;
	int i;
	for(i=1;i<=n;i++)
	{
		cin>>cabin[i].col;
		cin>>cabin[i].l;
		cin>>cabin[i].r;
		suffix[cabin[i].col]++;
	}
	for(i=1;i<=n;i++) 
	{
		suffix[cabin[i].col]--;
		update(cabin[i].col,-prefix[cabin[i].col]);//减去作为右边的匹配数
		cout<<query(cabin[i].r)-query(cabin[i].l-1)<<' ';
		prefix[cabin[i].col]++;
		update(cabin[i].col,suffix[cabin[i].col]);//加上作为左边的匹配数
	}
}
int main()
{
	ios::sync_with_stdio(false);
	solve();
	return 0;
}

I-匹配星星

题目描述

天上有n颗星星，每颗星星有二维坐标(xi,yi)(x_i, y_i)，还有一个属性值ziz_i，若两颗星星A, B满足xA<xBx_A<x_B且yA<yBy_A <y_B且zA<zBz_A < z_B，则这两颗星星可以配成一对，每颗星星最多只能在一对之中，求最多能配成多少对星星。

输入描述

第一行一个正整数n，表示星星的个数。
接下来n行，每行 3 个整数xi,yi,zix_i, y_i, z_i，表示一颗星星。

输出描述

一行一个整数，表示答案。

示例1

输入
2
1 1 0
2 2 1
输出
1

示例2

输入
2
1 1 1
2 2 1
输出
0

思路

首先要让所有星星按照xx从小到大排序。
用multiset设置一个候选池pool，储存星星的坐标yy，用multiset的好处是使坐标yy有序，且是从小到大排列的。
然后做一次遍历(for i 1 to n),如果zi=0z_i=0，那么将这颗星星放入候选池；如果zi=1z_i=1，那么我们就要从pool中选取一颗星星与之配对。由于xx已经从小到大排序，所以放入pool的星星的坐标xx都比xix_i小；因为pool中yy从小到大排列，于是我们只要二分找到第一个比yiy_i大的坐标yy，pool中前面的那几颗星星都可与之配对。
这样一种贪心的策略显然是可行的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
void solve()
{
	struct node
	{
		int x,y,z;
		bool operator < (const node &rhs) const
		{
			if(x==rhs.x) return z>rhs.z;
			else return x<rhs.x;
		}
	}star[100002];
	int n;
	cin>>n;
	int i;
	for(i=1;i<=n;i++) cin>>star[i].x>>star[i].y>>star[i].z;
	sort(star+1,star+1+n);
	multiset<int>pool;//备选区
	multiset<int>::iterator it;
	int ans=0;
	for(i=1;i<=n;i++)
	{
		if(star[i].z)
		{
			it=pool.lower_bound(star[i].y);
			if(it!=pool.begin())
			{
				pool.erase(--it);
				ans++;
			}
		}
		else
		{
			pool.insert(star[i].y);
		}
	 }
	 cout<<ans; 
}
int main()
{
	ios::sync_with_stdio(false);
	solve();
	return 0;
}