1003

Kanade's sum

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2097 Accepted Submission(s): 164

Problem Description

Give you an array

Input

There is only one integer T on first line.

For each test case,there are only two integers

Output

For each test case,output an integer, which means the answer.

Sample Input

Sample Output

对于每一个i，找到他前面k个比他大的，找到后面k个比他大的。这样，a[i]是第k大的区间可以变为：前面0个比他大，后面k个；前面1个，后面k-1个……，统计这样的区间有多少，就是a[i]的贡献。

普遍做法是从小到大枚举 $x$ ，每次维护一个链表，链表里只有 $> = x$ 的数，那么往左往右找只要暴力跳次，删除也是 $O (1)$ 的。

时间复杂度：

x从1开始找，因为1左右的都是比它大的数，找完后ans加上k大值是 1 的区间数 * 1 ,然后在数组里把 1 删除，然后找比枚举 1 的下一位，因为1 已经被删除了，所以剩下的都是比 2 大的数字了，又用同样的方法，直到n - k +1。所以查找的时候顺序不是按照输入的顺序找每个的k大值，而是按照从1的k大值、2的k大值…n的k大值这样的顺序找的。

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<cmath>  
#include<algorithm>  
using namespace std;  
typedef long long LL;  
const int INF=0x3f3f3f3f;  
const LL MOD=1e9+7;  
const int MAXN=1e6+7;  
int a[MAXN],pos[MAXN];  
int s[MAXN],t[MAXN];  
int pre[MAXN],nxt[MAXN];  
int n,k;  
  
void erase(int x)//把下标为x的这个数从数组中删掉   
{  
    int pp=pre[x],nn=nxt[x];  
    if(pre[x]) nxt[pre[x]]=nn;  
    if(nxt[x]<=n) pre[nxt[x]]=pp;  
    pre[x]=nxt[x]=0;  
}  
  
int main()  
{  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%d%d",&n,&k);  
        for(int i=1;i<=n;++i)  
        {  
            scanf("%d",&a[i]);  
            pos[a[i]]=i;//每一个数对应的下标   
        }  
        for(int i=1;i<=n;++i)  
        {  
            pre[i]=i-1;  
            nxt[i]=i+1;  
        }  
//        for(int i=1;i<=n;++i)  
//        {  
//            cout<<pre[i]<<" "<<nxt[i]<<endl;  
//        }  
        LL ans=0;  
        for(int num=1;num<=n-k+1;++num)  
        {  
            int p=pos[num];//cout<<p<<endl;  
            int s0=0,t0=0;  
            for(int d=p;d&&s0<=k;d=pre[d]) {  
                s[++s0]=d;  
                //printf("s[%d]=%d\n",s0,s[s0]);  
            }  
            for(int d=p;d!=n+1&&t0<=k;d=nxt[d]) {  
                t[++t0]=d;  
                //printf("t[%d]=%d\n",t0,t[t0]);  
            }  
            s[++s0]=0;t[++t0]=n+1;  
            //cout<<endl;  
              
              
            for(int i=1;i<=s0-1;++i)  
            {  
                if(k+1-i<=t0-1&&k+1-i>=1)  
                {  
                    ans+=(LL)(t[k+1-i+1]-t[k+1-i])*(s[i]-s[i+1])*num;  
                }  
            }  
            erase(p);  
        }  
        printf("%lld\n",ans);  
    }  
    return 0;  
}

1005（斯坦纳树待补）

求各个子树的size 再乘以结点的权值。

1008

RXD and math

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1832 Accepted Submission(s): 745

Problem Description

RXD is a good mathematician.
One day he wants to calculate:

Input

There are several test cases, please keep reading until EOF.
There are exact 10000 cases.
For each test case, there are 2 numbers

Output

For each test case, output "Case #x: y", which means the test case number and the answer.

Sample Input

  
   10 10

Sample Output

  
   Case #1: 999999937

注意到一个数字必然会被唯一表示成 $a^2*b$ 的形式.其中 $∣ μ (b) ∣ = 1$ 。所以这个式子会把 $1, n^k]$ 的每个整数恰好算一次. 所以答案就是 $n^k$ ,快速幂即可. 时间复杂度 $O (lo g k)。注意n的范围到了longlong的最大值，乘法时会爆掉，所以要用到快速幂取模和快速乘取模。$

#include<bits/stdc++.h>
#define Mo 1000000007
using namespace std;
typedef long long LL;

//LL fast_multi(LL m, LL n, LL mod)//快速乘法 
//{
//    LL ans = 0;//注意初始化是0，不是1 
//    while (n)
//    {
//        if (n & 1)
//            ans += m;
//        m = (m + m) % mod;//和快速幂一样，只不过这里是加 
//        m %= mod;//取模，不要超出范围 
//        ans %= mod;
//        n >>= 1;
//    }
//    return ans;
//}

LL fast_multi(LL x,LL y,LL m){
    if(y==0)return 0;
    if(y==1)return x%m;
    LL res;
    res=fast_multi(x,y>>1,m);
    if((y&1)==1)return (res+res+x)%m;
    else return (res+res)%m;
}
//LL fast_multi(long long x,long long y,long long mod)
//{
//long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
//return tmp<0 ? tmp+mod : tmp;
//}

LL fast_pow(LL a, LL n, LL mod)//快速幂 
{
    LL ans = 1;
    while (n)
    {
        if (n & 1)
            ans = fast_multi(ans, a, mod);//不能直接乘 
        a = fast_multi(a, a, mod);
        ans %= mod;
        a %= mod;
        n >>= 1;
    }
    return ans;
}

int main(){
//    freopen("out.txt","r",stdin);
    
    long long n,k;
    int cnt =1;
    while(~scanf("%lld%lld",&n,&k)){        
        cout<<"Case #"<<cnt++<<": "<<fast_pow(n,k,1000000007)<<endl;
    }
    return 0;
}

1011

RXD's date

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1426 Accepted Submission(s): 1085

Problem Description

As we all know that RXD is a life winner, therefore he always goes out, dating with his female friends.
Nevertheless, it is a pity that his female friends don't like extremely hot temperature. Due to this fact, they would not come out if it is higher than 35 degrees.
RXD is omni-potent, so he could precisely predict the temperature in the next

Input

There is only one test case.

The first line consists of one integer

Output

Output an integer which means the answer.

Sample Input

  
   5

33 34 35 36 37

Sample Output

签到题，统计即可。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        int cnt=0;
        for(int i=0;i<n;i++){
            int aa;
            scanf("%d",&aa);
            if(aa<=35)cnt++;
        }
        printf("%d\n",cnt);        
    }
    return 0;
}

官方题解

[多校补题]2017 Multi-University Training Contest 3 solutions BY 洪华敦

1003

Kanade's sum

1005（斯坦纳树 待补）

1008

RXD and math

1011

RXD's date

1005（斯坦纳树待补）