2021XTU程设考试

我是个菜鸡,天天被大佬吊打,这次考试的自己也只做出了第一题,惨遭挂科

xtu 1385 面积

正方形边长为1,E是对角线BD上一点，F是边AB上一点，已知|DE|=a/b|DB|,|BF|=c/d|AB|，求△CEF的面积。

思路:推公式,注意为负数的情况

#include<stdio.h>#include<algorithm>usingnamespace std;intmain(){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);}return0;}

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的可以不用管

#include<iostream>#pragmacomment(linker,"/STACK:102400000,102400000")usingnamespace std;#defineDebug(x) cout<<#x<<':'<<x<<endltypedeflonglong ll;#defineINF0x7fffffff//10^9级别，不到2^32#definemo20011#definemaxn10000
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++;elsereturn(x+i)%mo;}  
        re[(x+i)%mo]=n;return(x+i)%mo;}}voidinit(){//哈希表初始化for(ll i=0;i<mo;i++)  re[i]=INF;}intmain(){
    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;}return0;}

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了我不知道什么原因

#include<bits/stdc++.h>#pragmacomment(linker,"/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题usingnamespace std;#defineDebug(x) cout<<#x<<':'<<x<<endltypedeflonglong ll;#defineINF0x7fffffff//10^9级别，不到2^32const ll maxn=1e9;intmain(){
    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];//Debug(re[step-1]);}}}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++){//Debug(re[i]);if(re[i]==re[i-1]+1){
                    length++;if(length>maxl)  maxl=length;}else  length=1;}
            cout<<maxl<<endl;}}return0;}

xtu 1388 积木

积木块都是相同的立方体，一共有n列积木堆，这n列积木排成一排，每堆上是ai个积木堆叠起来，并且保证从左到右，每列的积木数是非递减的。

现在你还有k个积木块，请把这k个积木块放到积木上（可以只用部分积木块，但不能堆新的列）。你想的到一个连续的积木列，并使得这些积木列具有相同的高度。

请问你能得到这样的积木列的最大宽度？

思路:
最长区间问题,容易想到尺取,要用尺取,序列就得满足单调性,这题随着区间长度递增,k值是递增的,满足单调性.
具体来说就是用两个指针,一个右指针指向区间右边端点,一个左指针指向区间左边端点,用sum值记录这个区间内满足连续积木列所需的木块数,当sum<=k时,右指针右移,区间长度+1,当sum>k时,左指针右移,区间长度-1.记录下满足条件的最大长度

小提示:“巨大的输入量，请使用stdio.h头文件，并使用C风格的输入”,这句话在xtu oj经常有,但其实关了同步,用cin也不是很慢.像这道题就是.

#include<bits/stdc++.h>#pragmacomment(linker,"/STACK:102400000,102400000")usingnamespace std;#defineDebug(x) cout<<#x<<':'<<x<<endltypedef __int64 ll;#defineINF0x7fffffff//10^9级别，不到2^32const ll maxn=10000+11;
ll ar[maxn];intmain(){
    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;}return0;}

另一个思路:最长区间长度,由关键词最长,也容易想到二分,就是二分枚举最大宽度,对于每个宽度check下是否符合要求

xtu 1389 二叉查找树

n个元素，依次插入一颗初始为空的二叉查找树。对于第i个元素，其所在二叉查找书的左右子树深度差的绝对值为di，求max{di}。

板子题,直接套数据结构书上的模板就行了,思路没啥好讲的

#include<stdio.h>#include<algorithm>usingnamespace std;typedefstructNode* BST;structNode{int num;
    BST left;
    BST right;};intGetHeight(BST a);
BST Insert(BST a,int b);
BST Free1(BST a);int max_num;intmain(){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);//free大大减少OJ上的空间}return0;}intGetHeight(BST a){if(!a)return0;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(structNode));
        a->num=b;
        a->left=a->right=NULL;}else{if(b>a->num)  a->right=Insert(a->right,b);elseif(b<a->num)  a->left=Insert(a->left,b);//b==a->num情况不考虑}return a;}
BST Free1(BST a){if(a){//若未考虑非空情况，会导致出错！if(a->left==NULL&& a->right==NULL){free(a);
            a=NULL;returnNULL;}  
        a->left=Free1(a->left);
        a->right=Free1(a->right);free(a);
        a=NULL;returnNULL;}elsereturnNULL;}

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.

代码:

/*** 
 * @Practice Win
 * @打h_1,h_2
 */#include<bits/stdc++.h>#pragmacomment(linker,"/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题usingnamespace std;#defineDebug(x) cout<<#x<<':'<<x<<endltypedeflonglong ll;#defineINF0x7fffffff//10^9级别，不到2^32
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;}voidsolve(ll l,ll r,ll power){//递归处理，l是串起点，r是终点，power是串乘以的倍数//关于power，因为括号后面可以接数字，表示几倍，所有需要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;}voidinit(){memset(cnt,0,sizeof(cnt));//cnt数组初始化}voidout(){//输出函数for(char i='a';i<='z';i++){if(cnt[i]==0)continue;
        cout<<i<<" : "<<cnt[i]<<endl;}
    cout<<endl;}intmain(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);while(cin>>sr){init();solve(0,sr.length(),1);out();}return0;}

头一次发现自己也能写出来这么好看的且规范的代码了,main函数里几个函数就搞定了(窃喜)