Dylan's Blog
0%

Posted on Edited on In

问题描述

大意就是：给你一个长度为n(n<=10000)的序列，再給你m(m<=20000)个询问，问你在给定区间[l,r]中的众数。（题目强制要求在线）

输入

第一行n, m 第二行给你序列（序列元素小于10^9） 接下来m行每行两个数l, r。

输出

m行，每行输出第m个询问的答案。

思路

由于众数是不方便进行区间合并的，因此不能够使用线段树或树状数组等数据结构。在这种情况下，分块是一种可能的选择。

分块时，我们考虑一个区间的众数只可能是：包含在区间中所有完整块的众数或者是包含在不完整的块中的数。这样，对于任意一个区间我们把范围缩小到了$2*size$($size$为块的大小)个数。

我们可以预处理出第i个完整块到第j个完整块中的众数，储存为f[i][j]。然后我们就考虑如何计算这些数在区间中的出现次数。我们可以用vector储存下标，然后用二分查找找出区间内的元素个数，这个即是该数在区间内的出现次数。

分析一下复杂度，设一个完整块的大小为size。处理询问的复杂度是$m*size*log(n)$，预处理的复杂度是$n*n/size$，这样size在大约200差不多就不会TLE了。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#define MAXN 40005
using namespace std;

int n, m, size, num, id, a[MAXN], pos[MAXN], L[MAXN], R[MAXN], ans;
int cnt[MAXN], val[MAXN], f[500][500];

map<int, int> mmp;
vector<int> vec[MAXN];

void init()
{
    size=sqrt(n), num=n/size;
    for(int i=1; i<=num; i++) L[i]=(i-1)*size+1, R[i]=i*size;
    if(R[num]<n) {L[++num]=R[num-1]+1; R[num]=n;}
    for(int i=1; i<=num; i++) for(int j=L[i]; j<=R[i]; j++) pos[j]=i;

    for(int i=1; i<=num; i++)
    {
        int maxn=0, ans=0;
        memset(cnt, 0, sizeof(cnt));
        for(int j=L[i]; j<=n; j++)
        {
            cnt[a[j]]++;
            int p=pos[j];
            if(cnt[a[j]]>maxn || (cnt[a[j]]==maxn && val[a[j]]<val[ans])) ans=a[j], maxn=cnt[a[j]];
            f[i][p]=ans;
        }
    }
}

int cal(int l, int r, int x)
{
    return upper_bound(vec[x].begin(), vec[x].end(), r)-lower_bound(vec[x].begin(), vec[x].end(), l);
}

int query(int l, int r)
{
    int ans=0, maxn=0, x=pos[l], y=pos[r];
    if(x==y)
    {
        for(int i=l; i<=r; i++)
        {
            int t=cal(l, r, a[i]);
            if(t>maxn || (t==maxn && val[a[i]]<val[ans])) ans=a[i], maxn=t;
        }
    }
    else
    {
        ans=f[x+1][y-1];
        maxn=cal(l, r, ans);
        for(int i=l; i<=R[x]; i++)
        {
            int t=cal(l, r, a[i]);
            if(t>maxn || (t==maxn && val[a[i]]<val[ans])) ans=a[i], maxn=t;
        }
        for(int i=L[y]; i<=r; i++)
        {
            int t=cal(l, r, a[i]);
            if(t>maxn || (t==maxn && val[a[i]]<val[ans])) ans=a[i], maxn=t;
        }
    }
    return ans;
}

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a2.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
        if(!mmp[a[i]])
        {
            mmp[a[i]]= ++id;
            val[id]=a[i];
        }
        a[i]=mmp[a[i]];
        vec[a[i]].push_back(i);
    }
    init();
    for(int i=1; i<=m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l=(l+ans-1)%n+1;
        r=(r+ans-1)%n+1;
        if(l>r) swap(l, r);
        ans=val[query(l, r)];
        printf("%d\n", ans);
    }
}

Posted on Edited on In

问题描述

有一个1-n的序列，你只知道在每一位之前有多少个数字比它小，请你求出这个序列。

输入

第一行n， 接下来n-1行，第i行表示在第i个数之前有多少个数比它小。

输出

输出这个序列

思路

不难想到，这个序列我们可以从后往前推。我们设num[i]为第i个数之前有多少个数比它小。

因为最后一个数有num[n]个比它小，那它一定是num[n]+1。然后继续递推倒数第n-1个数，它就是除了num[n]+1中的第num[n-1]+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
32
33
34
35
36
37
38
39
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 8005
using namespace std;

int n, num[MAXN], t[MAXN], ans[MAXN];

void add(int x, int y) {for(; x<=n; x+=(x&-x)) t[x]+=y;}
int sum(int x) {int y=0; for(; x; x-=(x&-x)) y+=t[x]; return y;} 

int search(int x)
{
    int l=1, r=n, ans;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(sum(mid)>=x) ans=mid, r=mid-1;
        else l=mid+1;
    }
    return ans;
}

int main()
{
    scanf("%d", &n);
    add(1, 1);
    for(int i=2; i<=n; i++)
    {
        scanf("%d", &num[i]);
        add(i, 1);
    }
    for(int i=n; i>=1; i--)
    {
        ans[i]=search(num[i]+1);
        add(ans[i], -1);
    }
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
}

线段树

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 8005
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
using namespace std;

int n, num[MAXN], t[MAXN*4], ans[MAXN];

void build(int rt, int l, int r)
{
    t[rt]=r-l+1;
    if(l==r) return;
    build(ls, l, mid);
    build(rs, mid+1, r);
}

int query(int rt, int l, int r, int x)
{
    t[rt]--;
    if(l==r) return l;
    if(x>t[ls]) return query(rs, mid+1, r, x-t[ls]);
    else return query(ls, l, mid, x);
}

int main()
{
    scanf("%d", &n);
    build(1, 1, n);
    for(int i=2; i<=n; i++) scanf("%d", &num[i]);
    for(int i=n; i>=1; i--) ans[i]=query(1, 1, n, num[i]+1);
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
}

Posted on Edited on In

6月3日 AtCoder Grand Contest 025 题目链接：https://agc025.contest.atcoder.jp/assignments

A - Digits Sum

直接枚举就好了，不多说。

B - RGB Coloring

思路： 思路比较巧妙。我们可以将题意进行转化，你可以在n层中选取任意a层涂红，再从n层中选取任意b层涂蓝（如果一层既涂成红，又涂成蓝，那就相当与原题中的涂成绿）。

这样就把原来三种颜色变成两种。于是只要枚举a, b,答案就是之和，其中满足A*a+B*b=K。

代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define LL long long
#define MAXN 300005
#define p 998244353
using namespace std;

LL n, a, b, k, ans, fac[MAXN], inv[MAXN];

LL ksm(LL x, LL y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=(x*sum)%p;
        x=(x*x)%p; y>>=1;
    }
    return sum;
}

void init()
{
    fac[0]=fac[1]=1;
    inv[0]=inv[1]=1;
    for(int i=2; i<=n; i++) inv[i]=(p-p/i)*inv[p%i]%p;
    for(int i=2; i<=n; i++) fac[i]=fac[i-1]*i%p;
    for(int i=2; i<=n; i++) inv[i]=inv[i-1]*inv[i]%p; 
}

LL com(int n, int m)
{
    if(m>n) return 0; 
    return fac[n]*inv[n-m]%p*inv[m]%p;
}

int main()
{
    scanf("%lld%lld%lld%lld", &n, &a, &b, &k);
    if(k==0) {printf("1\n"); return 0;}
    init();
    for(int i=1; a*i<=k && i<=n; i++)
    {
        if((k-a*i)%b!=0) continue;
        int j=(k-a*i)/b;
        ans=(com(n, i)*com(n, j)%p+ans)%p;
    }
    printf("%lld\n", ans);
}

C - Interval Game

思路： 这是一个贪心，每次Aoki一定会选择让Takahashi行走距离最长的区间，而Takahashi一定会走到区间上最靠近自己的端点（如果Takahashi在区间中，则不动）。

因此，Aoki会选择左端点最右或右端点最左的区间，他轮流选择 左区间和右区间，这样使得Takahashi走的最长。

长度就比较好计算（细节见代码），但要注意由于起点和终点在原点，所以要把[0,0]这个区间加入进去。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
#define MAXN 100005
#define LL long long 
using namespace std;

LL n, ans, l[MAXN], r[MAXN];

bool CMP1(LL x, LL y) {return x>y;}
bool CMP2(LL x, LL y) {return x<y;}

int main()
{
    scanf("%lld", &n);
    for(int i=1; i<=n; i++) scanf("%lld%lld", &l[i], &r[i]);
    sort(l, l+n+1, CMP1);
    sort(r, r+n+1, CMP2);
    for(int i=0; i<=n; i++) if(l[i]>r[i]) ans+=l[i]-r[i];
    printf("%lld\n", ans*2);
}

D - Choosing Points

思路： 这其实是一个二分图染色，假设一个点为白色，那么我们可以将与它相距$\sqrt{D}$的点染成黑色，那么这样永远不会有两种颜色相同的点距离为$\sqrt{D}$（由于是二分图，染色是不会冲突）。二分图的证明可以看原题题解，证明了一大堆

于是我们可以依据D1和D2，将这个图进行两次染色。我们可以根据我们染的颜色，确定出n^2个点。原题题解也证明了保证有n^2个点符合要求。 代码：

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
#include <bits/stdc++.h>
#define MAXN 600
using namespace std;

int n, m, cnt, d[5], col[MAXN][MAXN][2];
bool vis[MAXN][MAXN][2];

void dfs(int x, int y, int a, int b)
{
    if(x<0 || x>m || y<0 || y>m || vis[x][y][a]) return;
    vis[x][y][a]=true; col[x][y][a]=b;
    for(int i=0; i*i<=d[a]; i++)
    {
        int j=sqrt(d[a]-i*i);
        if(i*i+j*j!=d[a]) continue;
        dfs(x+i, y+j, a, 3-b);
        dfs(x-i, y+j, a, 3-b);
        dfs(x+i, y-j, a, 3-b);
        dfs(x-i, y-j, a, 3-b);
    }
}

void debug()
{
    for(int i=0; i<=m; i++)
    {
        for(int j=0; j<=m; j++) printf("%d ", col[i][j][0]);
        printf("\n");
    }
    printf("\n\n");
    for(int i=0; i<=m; i++)
    {
        for(int j=0; j<=m; j++) printf("%d ", col[i][j][1]);
        printf("\n");
    }
}

int main()
{
    scanf("%d%d%d", &n, &d[0], &d[1]);
    m=n*2-1;
    for(int i=0; i<=m; i++)
    for(int j=0; j<=m; j++)
    {
        if(!vis[i][j][0]) dfs(i, j, 0, 1);
        if(!vis[i][j][1]) dfs(i, j, 1, 1);
    }
    for(int i=0; i<=m; i++)
    for(int j=0; j<=m; j++)
    {
        if(col[i][j][0]==1 && col[i][j][1]==1)
        {
            printf("%d %d \n", i, j);
            if(++cnt==n*n) return 0;
        }
    }
}

Posted on Edited on In

5月6日，CodeForces round 963 题目链接：http://codeforces.com/contest/963

总体难度蛮大，题目特别好，特别考察思维能力。

A - Alternating Sum

思路： 开始确实没有什么思路。看数据范围a,b,n都很大，只有k小一点。所以复杂度应该和k有关，与a,b,n无关。

然后往这个思路去想，就可以发现所求式子是一个等比数列。由于符号k个一循环，所以我们可以将每一个循环看作一项。然后就计算式子的首项和公比，运用等比数列求和公式求出答案。

代码：

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 <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAXN 100005
#define p 1000000009
#define LL long long
using namespace std;

LL n, a, b, k, a1, q, ans;
char opt[MAXN];

LL ksm(LL x, LL y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=(sum*x)%p;
        y>>=1; x=(x*x)%p;
    }
    return sum%p;
}

int main()
{
    scanf("%I64d%I64d%I64d%I64d", &n, &a, &b, &k);
    scanf("%s", opt);
    for(int i=0; i<k; i++) //计算首项
    {
        if(opt[i]=='+') a1=(a1+(ksm(a, n-i)*ksm(b, i))%p)%p;
        else a1=(a1-(ksm(a, n-i)*ksm(b, i))%p)%p;
        if(a1<0) a1+=p;
    }
    q=ksm(b, k)*ksm(ksm(a, k), p-2)%p; //计算公比
    if(q!=1) ans=a1*(ksm(q, (n+1)/k)-1)%p*ksm(q-1, p-2)%p; //用数学公式算出答案
    else ans=a1*(n+1)/k%p; //注意特判公比为1
    printf("%I64d\n", (ans+p)%p);
}

B - Destruction of a Tree

思路： 这道题也比较思维特别巧妙，我个人觉得其实有一点像树形DP。

首先从根节点遍历一遍树，用一个数组记录它儿子的个数。递归回去时如果它儿子是奇数个，那么该节点的度数就是偶数，所以可以将该节点删去，并将父亲节点的儿子个数-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
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAXN 200005
using namespace std;

struct Edge {int to, next;} edge[MAXN*2];

int n, t, root, cnt, head[MAXN], son[MAXN], sta[MAXN], top;

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs(int x, int f)
{
    son[f]++;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to!=f) dfs(to, x);
    }
    if(son[x]%2) son[f]--;
}

void dfs1(int x, int f) //输出方案
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to!=f && son[to]%2) dfs1(to, x);
    }
    printf("%d\n", x);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to!=f && son[to]%2==0) dfs1(to, x);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &t);
        if(t==0) root=i;
        else
        {
            addedge(i, t);
            addedge(t, i);
        }
    }
    dfs(root, 0);
    if(son[root]%2) printf("NO\n");
    else
    {
        printf("YES\n");
        dfs1(root, 0);
    }
}

C - Cutting Rectangle

思路： 首先如何计算答案并不难想到。求出所有c[i]的GCD，然后该数的约数个数就是答案。

但是判断无解情况就比较难想了。考虑能够构成矩形的条件，所有大矩形一定是通过若干单位矩形构成的。接下来我们便考虑单位矩形，当ｗ相同时，不同的ｈ在单位矩形中的个数与它的总个数是成比例的。也就是w[i]的数量：总数量＝c[i]:h[i]的数量。只要有任何一种矩形不满足这个式子，就不存在单位矩形，即是无解。

代码：

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
#include <bits/stdc++.h>
#define MAXN 200005
#define LL long long
using namespace std;

LL n, sum, temp, ans, w[MAXN], h[MAXN], c[MAXN];
map<LL, LL> a, b; 

LL gcd(LL x, LL y)
{
    if(y==0) return x;
    return gcd(y, x%y); 
} 

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld%lld%lld", &w[i], &h[i], &c[i]);
        a[w[i]]+=c[i]; b[h[i]]+=c[i];
        sum+=c[i]; temp=gcd(temp, c[i]);
    }
    for(int i=1; i<=n; i++) if(fabs((double)a[w[i]]/sum-(double)c[i]/b[h[i]])>1e-16)
    {
        printf("0");
        return 0;
    }
    for(LL i=1; i*i<=temp; i++)
    {
        if(temp%i==0) ans+=2;
        if(i*i==temp) ans--;
    }
    printf("%lld\n", ans);
}

Posted on Edited on In

问题描述

给你一个长为n(n<=15)的序列，你需要将它排序（从小到大）。

你可以从中选取任意一段将它取出，并插入序列中任意位置。问你最少需要多少次这种操作。

输入

第一行给出数据组数T。 每组数据第一行给出n。 接下来一行给出你n个数（这些数是1-n的排列）。

输出

对于每一组数据输出最小的操作次数。 如果操作次数大于或等于5，输出“5 or more”

思路

看数据范围就知道是搜索，而且时限也很宽。

我们分析一下普通的搜索，枚举任意一段共有n*(n-1)/2种情况，枚举插入的位置共有n种情况。所以一次操作就有O(n^3)复杂度，最多要枚举4次操作，所以总复杂度是肯定不符合要求的。

但是我们可以使用IDA* 搜索。假如a[i]+1!=a[i+1]则称这是一个错误后缀，如果一个序列没有错误后缀，则它是有序的。然后我们考虑每一次操作最优只能减少3个错误后缀，所以操作数一定大于等于错误后缀数/3.因此我们将错误后缀数/3作为估值函数。其他的实现就比较简单了。

细节

  1. 循环中变量的范围一定不要弄错了
  2. 估值函数不要写错了，是（cnt+2)/3

代码

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 
#include 
#include 
#define MAXN 200
using namespace std;

int T, n, a[MAXN], t[MAXN], ans;
bool flag;

int h(int *a)
{
    int cnt=0; 
    for(int i=1; i
void move(int x, int y, int len, int *temp)
{
    for(int i=0; i
bool dfs(int step, int *a)
{
    int temp[MAXN];
    if(h(a)==0) {flag=true; return true;}
    if(h(a)+step>ans) return false;
    for(int len=1; len
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        flag=false;
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        for(ans=0; ans<=4; ans++) if(dfs(0, a))
        {
            printf("%d\n", ans);
            break;
        }
        if(!flag) printf("5 or more\n");
    }
}