multi多校-3

自用笔记算法

muti多校-3

HDU 6058

题目要求

求数组中所有连续区间的k大数之和

参考AC代码

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
#include<cstdio>
typedef long long ll;
const int N=500010;
int Case,n,K,i,a[N],pos[N],pre[N],nxt[N];
ll ans;
inline void del(int i){
  pre[nxt[i]]=pre[i];
  nxt[pre[i]]=nxt[i];
}
inline ll solve(int x){
  static int a[100],b[100];
  int i,ca=0,cb=0;
  for(i=x;i;i=pre[i]){
    a[++ca]=i-pre[i];
    if(ca==K)break;
  }
  for(i=x;i<=n;i=nxt[i]){
    b[++cb]=nxt[i]-i;
    if(cb==K)break;
  }
  ll t=0;
  for(i=1;i<=ca;i++)if(K-i+1<=cb) t+=1LL*a[i]*b[K-i+1];
  return t;
}
int main(){
//    freopen("input.txt","r",stdin);
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&K);
    for(i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i;
    for(i=0;i<=n+1;i++)pre[i]=i-1,nxt[i]=i+1;
    pre[0]=0;
    nxt[n+1]=n+1;
    ans=0;
    for(i=1;i<=n;i++){
      int x=pos[i];
      ans+=solve(x)*i;
      del(x);
    }
    printf("%lld\n",ans);
  }
}

思路

用双向链表模拟
pre和next模拟指针
对数字hash处理记录位置 从1开始处理 处理好之后把1删除处理2 因为1对2的处理没有影响 后续相同
删除操作需要修改pre和next数组
对于每个位置预处理左边和右边比它大的k个数字
注意：i==1表示向左取一个段 并未取到端点 若a[i]=1表示左端点未取 自然做乘法操作时乘1
若a[i]>1表示中间有小于它的数字 自然有a[i]种情况
a和b代表段长并未是总长 因为如i取到2 说明必取1个点 所以能变化的区间只有这个点的后面的段了
综上 i是取的段数并未取段末的点 所以不能在k==1时break 也需要用k+i-i来判断右边的段数

HDU 6060

题目要求

给出一颗n个节点的树，要求将2-n号节点分成k部分，然后再将每一部分加上1号节点，定义每一部分的val为其中的点在原图上的最小斯坦纳树，问总的val最大可能是多少。

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1000050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int n,k;
LL ans;
int sz[maxn];
struct node{
    int to,w;
    node(int to,int w):to(to),w(w){}
};
vector<node>e[maxn];
void dfs(int id,int fa,int ww){
    sz[id]=1;
    for(int i=0;i<e[id].size();i++){
        int next=e[id][i].to,we=e[id][i].w;
        if(next==fa) continue;
        dfs(next,id,we);
        sz[id]+=sz[next];
    }
    int temp=min(k,sz[id]);
    ans+=(LL)ww*(LL)temp;
}
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    while(cin>>n>>k){
        for(int i=0;i<=n;i++) e[i].clear();
        mm(sz,0),ans=0;
        for(int i=1;i<=n-1;i++){
            int x,y,z;
            cin>>x>>y>>z;
            e[x].pb(node(y,z));
            e[y].pb(node(x,z));
        }
        dfs(1,0,0);
        cout<<ans<<endl;
    }
    return 0;
}

思路


ans开LL

HDU 6063

题目要求

计算

期中u为莫比乌斯函数

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int flag=1;
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    LL n,k;
    while(cin>>n>>k){
        cout<<"Case #"<<flag++<<": ";
        n%=mod;
        cout<<qpow(n,k)<<endl;
    }
    return 0;
}

思路

打表可以发现答案就是n^k
注意n需要先mod

HDU 6066

题目要求

求数组中小于等于35的个数

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    int sum=0;
    for(int i=1;i<=t;i++){
        int x;
        cin>>x;
        if(x<=35) sum++;
    }
    cout<<sum<<endl;
    return 0;
}

思路

水题

本文标题:multi多校-3

文章作者:Hippopmonkey

发布时间:2017-08-02, 00:00:08

最后更新:2017-08-02, 11:24:45

原始链接:http://xuboming8.github.io/2017/08/02/multi多校-3/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. muti多校-3
    1. 1.1. HDU 6058
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6060
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 6063
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 6066
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
|