好菜啊，就做了一道题，挂科了555
赶忙来补题
xtu 1385 面积
正方形边长为1,E是对角线BD上一点，F是边AB上一点，已知|DE|=a/b|DB|,|BF|=c/d|AB|，求△CEF的面积。
思路:推公式,注意为负数的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--){
int a,b,c,d;
scanf("%d %d %d %d",&a,&b,&c,&d);
int m=b*d-a*c-a*d;
int n=2*b*d;
if(m==0){
printf("0\n");
continue;
}
if(m<0) m=abs(m);
int k=__gcd(m,n);
m/=k,n/=k;
printf("%d/%d\n",m,n);
}
return 0;
}
|
xtu 1386 彩球
有n个球，标号为1∼n，第i个球有的颜色为ci。你需要选择3个不同颜色的球，问有多少种不同的选择方案？
思路:先hash统计各个颜色气球数量(可以map,unordered_map,unordered_map应该不会超时,map不知道)
然后因为直接数三个不同色的很困难,这里就得用到间接法,但是谢大认为这是小学三年级知识,其实我们大部分人都没想到.
就是用从n个球中选出3个球的方案数(即组合数C n 选3) 减去 三球同色 减去 两球同色,即为三球不同色的方案数,复杂度是O(n)的,可以接受
坑点:64位如果是scanf输入记得用__int64,不然会wa,用cin的可以不用管
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
| #include<iostream>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
typedef long long ll;
#define INF 0x7fffffff
#define mo 20011
#define maxn 10000
ll re[mo+11];
inline ll hash1(ll n){
ll x=n%mo;
if(re[x]==INF) {re[x]=n;return x;}
else{
ll i=0;
while(re[(x+i)%mo]!=INF){
if(re[(x+i)%mo]!=n) i++;
else return (x+i)%mo;
}
re[(x+i)%mo]=n;
return (x+i)%mo;
}
}
void init(){
for(ll i=0;i<mo;i++) re[i]=INF;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll t;
cin>>t;
while(t--){
init();
ll co[mo+11]={0};
ll ar[mo+11]={0};
ll n;
cin>>n;
for(ll i=1;i<=n;i++){
ll t;cin>>t;
co[hash1(t)]++;
}
ll step=0;
for(ll i=0;i<mo;i++){
if(co[i]!=0){
ar[++step]=co[i];
}
}
ll ans=n*(n-1)*(n-2)/6;
for(ll i=1;i<=step;i++){
if(ar[i]>=3) ans=ans-ar[i]*(ar[i]-1)*(ar[i]-2)/6;
if(ar[i]>=2) ans=ans-ar[i]*(ar[i]-1)/2*(n-ar[i]);
}
cout<<ans<<endl;
}
return 0;
}
|
xtu 1387 完全区间
序列X由线性产生式 xn=axn−1+bxn−2,x0=x1=1 产生，
序列Y由线性产生式 yn=cyn−1+dyn−2,y0=y1=1 产生，
集合Z={x+y∣x∈X,y∈Y}。
现有区间[L,R]，求最长的子区间[l,r],满足L≤l≤r≤R,∀z∈[l,r],z∈Z。
思路：题目看似数据量很大，到10^9,我也是一开始被吓到了
其实不然，仔细分析
因为斐波那契数列增长很快，约为2的x次方，指数级别
所以x中最多到差不多50项，就会超出1e9次方，即x中最多50个元素
同理，y中最多也只有50个，那么z中最多就只有50*50个
可以枚举产生Z 复杂度可以接受
最后再在L~R区间内遍历一遍,找出最长子区间即可
坑点:最好用64位,不然容易爆int,很多人re了我不知道什么原因
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
| #include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
typedef long long ll;
#define INF 0x7fffffff
const ll maxn=1e9;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll t;
cin>>t;
while(t--){
ll a,b,c,d,l,r;
ll x[55]={1,1,1},y[55]={1,1,1};
ll re[2555],step=1;
cin>>a>>b>>c>>d>>l>>r;
ll l1=2,l2=2;
for(ll i=3;i<55;i++){
x[i]=a*x[i-1]+b*x[i-2];
l1++;
if(x[i]<=0 || x[i]>=1e9) break;
}
for(ll i=3;i<55;i++){
y[i]=c*y[i-1]+d*y[i-2];
l2++;
if(y[i]<=0 || y[i]>=1e9) break;
}
for(ll i=1;i<l1;i++){
for(ll j=1;j<l2;j++){
if(l<=x[i]+y[j] && x[i]+y[j]<=r){
re[step++]=x[i]+y[j];
}
}
}
sort(re+1,re+step);
step=unique(re+1,re+step)-(re+1);
if(step==0) cout<<0<<endl;
else{
ll length=1,maxl=1;
for(ll i=2;i<=step;i++){
if(re[i]==re[i-1]+1){
length++;
if(length>maxl) maxl=length;
}
else length=1;
}
cout<<maxl<<endl;
}
}
return 0;
}
|
xtu 1388 积木
积木块都是相同的立方体，一共有n列积木堆，这n列积木排成一排，每堆上是ai个积木堆叠起来，并且保证从左到右，每列的积木数是非递减的。
现在你还有k个积木块，请把这k个积木块放到积木上（可以只用部分积木块，但不能堆新的列）。你想的到一个连续的积木列，并使得这些积木列具有相同的高度。
请问你能得到这样的积木列的最大宽度？
思路:
最长区间问题,容易想到尺取,要用尺取,序列就得满足单调性,这题随着区间长度递增,k值是递增的,满足单调性.
具体来说就是用两个指针,一个右指针指向区间右边端点,一个左指针指向区间左边端点,用sum值记录这个区间内满足连续积木列所需的木块数,当sum<=k时,右指针右移,区间长度+1,当sum>k时,左指针右移,区间长度-1.记录下满足条件的最大长度
小提示:”巨大的输入量，请使用stdio.h头文件，并使用C风格的输入”,这句话在xtu oj经常有,但其实关了同步,用cin也不是很慢.像这道题就是.
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
| #include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
typedef __int64 ll;
#define INF 0x7fffffff
const ll maxn=10000+11;
ll ar[maxn];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
for(ll i=1;i<=n;i++) cin>>ar[i];
ll l=1,r=1,length,maxl,k1=0;
for(ll r=1;r<=n;r++){
if(r==1){
length=1;
maxl=1;
}
else{
if(ar[r]!=ar[r-1]) k1=k1+(r-l)*(ar[r]-ar[r-1]);
length++;
while(k1>k){
k1=k1-(ar[r]-ar[l]);
length--;
l++;
}
if(length>maxl) maxl=length;
}
}
cout<<maxl<<endl;
}
return 0;
}
|
另一个思路:最长区间长度,由关键词最长,也容易想到二分,就是二分枚举最大宽度,对于每个宽度check下是否符合要求
xtu 1389 二叉查找树
n个元素，依次插入一颗初始为空的二叉查找树。对于第i个元素，其所在二叉查找书的左右子树深度差的绝对值为di，求max{di}。
板子题,直接套数据结构书上的模板就行了,思路没啥好讲的
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
| #include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct Node * BST;
struct Node{
int num;
BST left;
BST right;
};
int GetHeight(BST a);
BST Insert(BST a,int b);
BST Free1(BST a);
int max_num;
int main(){
int t;
scanf("%d",&t);
while(t--){
max_num=0;
int n;
scanf("%d",&n);
BST root;
root=NULL;
for(int i=0;i<n;i++){
int b;
scanf("%d",&b);
root=Insert(root,b);
}
GetHeight(root);
printf("%d\n",max_num);
Free1(root);
}
return 0;
}
int GetHeight(BST a){
if(!a) return 0;
int d,max_2,hl,hr;
hl=GetHeight(a->left);
hr=GetHeight(a->right);
max_2=hl>hr?hl:hr;
d=abs(hr-hl);
if(d>max_num) max_num=d;
return (max_2+1);
}
BST Insert(BST a,int b){
if(!a){
a=(BST)malloc(sizeof(struct Node));
a->num=b;
a->left=a->right=NULL;
}
else{
if(b>a->num) a->right=Insert(a->right,b);
else if(b<a->num) a->left=Insert(a->left,b);
}
return a;
}
BST Free1(BST a){
if(a){
if(a->left==NULL && a->right==NULL){
free(a);
a=NULL;
return NULL;
}
a->left=Free1(a->left);
a->right=Free1(a->right);
free(a);
a=NULL;
return NULL;
}
else return NULL;
}
|
xtu 1390 字母计数
为了压缩一个只含小写英文字母的字符串，我们使用下面的方式表示它
任一字母c是表达式
任一字母c后接一个整数n也是一个表达式，表示把字母c重复n次，n是一个没有前导零的10进制整数，且 n≥2。
如果s1,s2是表达式，那么s1s2也是表达式。
S是一个表达式，那么(S)n也是表达式，表示将S这个表达式表示的字符串重复n次，n是一个没有前导零的10进制整数，且 n≥2。
比如表达式 ((a2b)2b)2a 表示字符串aabaabbaabaabba。
现在给你一个表达式，请统计一下其中各个字符出现的次数。
思路:很典型的递归处理,因为每次处理的字符串规则都是一样的,对于括号内的字符串,可以将它看成一个新字符串来递归处理.
坑点:oj的64位是真的坑,不小心用了个long long来用scanf转化输出字符就错了,建议大家在xtu oj上要么别用long long,要么用__int64,要么就不用scanf.
代码:
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
|
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
typedef long long ll;
#define INF 0x7fffffff
ll cnt[222];
string sr;
ll number(ll l,ll r){
ll ans=0;
for(ll i=l;i<r;i++){
ans=ans*10+sr[i]-'0';
}
return ans;
}
void solve(ll l,ll r,ll power){
for(ll i=l;i<r;i++){
if(sr[i]=='('){
ll t=1,p=i+1;
for(;p<r;p++){
if(t==0) break;
if(sr[p]=='(') t++;
if(sr[p]==')') t--;
}
if(p<r && '1'<=sr[p] && sr[p]<='9'){
ll l_t=p,r_t=p+1;
while(r_t<r && '0'<=sr[r_t] && sr[r_t]<='9') r_t++;
solve(i+1,p-1,number(l_t,r_t)*power);
i=r_t-1;
}
else{
solve(i+1,p-1,power);
i=p-1;
}
}
else{
if(i+1<r && '1'<=sr[i+1] && sr[i+1]<='9'){
ll l_t=i+1,r_t=i+2;
while(r_t<r && '0'<=sr[r_t] && sr[r_t]<='9') r_t++;
cnt[sr[i]]=cnt[sr[i]]+number(l_t,r_t)*power;
i=r_t-1;
}
else{
cnt[sr[i]]=cnt[sr[i]]+power;
}
}
}
return ;
}
void init(){
memset(cnt,0,sizeof(cnt));
}
void out(){
for(char i='a';i<='z';i++){
if(cnt[i]==0) continue;
cout<<i<<" : "<<cnt[i]<<endl;
}
cout<<endl;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
while(cin>>sr){
init();
solve(0,sr.length(),1);
out();
}
return 0;
}
|
头一次发现自己也能写出来这么优雅简介的代码了,main函数里几个函数就搞定了(窃喜)