xtuoj 0x11

Index

中位数

Code 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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[2000];

int cmp(const void *a,const void *b){
    return *(int *)a - *(int *)b;
}

int getMid(int head,int tail){
    int t[2000]={0},i,m=tail-head+1,flag=0;
    memcpy(t,a+head,(m)*(sizeof(int)));
    qsort(t,m,sizeof(int),cmp);
    for(int i=head;i<tail+1;i++){
        printf("%d ",t[i]);
    }
    puts("");
    if(a[(m)>>1]==t[(m)>>1]) return m/2;
    for(i=head;i<tail+1;i++){
        if(a[i]==t[(m)>>1]) break;
    }
    return i;
}

int dfs(int head,int tail,int weight,int ans){
    printf("head: %d tail: %d weight: %d ans: %d\n",head,tail,weight,ans);
    if(head==tail){
        printf("last_ans: %d\n",ans+a[head]*weight);
        return ans+a[head]*weight;
    }
    if(tail<0||head>tail) return ans;
    int mid=getMid(head,tail);
    printf("mid: %d\n",mid);
    ans+=a[mid]*weight;
    ans=dfs(head,mid-1,weight+1,ans);
    ans=dfs(mid+1,tail,weight+1,ans);
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        int ans=dfs(0,n-1,1,0);
        printf("%d\n",ans);
    }
    return 0;
}

我也不知道这个代码交上去对不对，因为这个代码的下标处理有问题，想了半天，必须要同时记录下标和值，得用结构体或者二维数组 ，懒得重构了，便用了老师的二维数组
Code 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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[2000],b[2000][2];

int cmp(const void *a,const void *b){
    return *(int *)a - *(int *)b;
}

int getMid(int head,int tail){
    int t=tail-head+1,i,j;
    for(i=head,j=0;j<=tail;i++,j++){
        b[j][0]=a[i];
        b[j][1]=i;
    }
    qsort(b,t,sizeof(b[0]),cmp);
    return b[t>>1][1];
}

int dfs(int head,int tail,int weight,int ans){
    if(head==tail){
        return ans+a[head]*weight;
    }
    if(tail<0||head>tail) return ans;
    int mid=getMid(head,tail);
    ans+=a[mid]*weight;
    ans=dfs(head,mid-1,weight+1,ans);
    ans=dfs(mid+1,tail,weight+1,ans);
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        int ans=dfs(0,n-1,1,0);
        printf("%d\n",ans);
    }
    return 0;
}

正统的递归板子
Code 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
39
40
41
42
43
44
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[2000],b[2000][2];

int cmp(const void *a,const void *b){
    return *(int *)a - *(int *)b;
}

int mid(int l,int r){
    int n=r-l+1,i,j;
    for(int i=l,j=0;j<=r;j++,i++){
        b[j][0]=a[i];
        b[j][1]=i;
    }
    qsort(b,n,sizeof(b[0]),cmp);
    return b[n>>1][1];
}

int dfs(int l,int r,int d){
    int ans=0;
    if(l==r) return ans+=a[l]*d;
    int k=mid(l,r);
    ans+=a[k]*d;
    if(l<k) ans+=dfs(l,k-1,d+1);
    if(r>k) ans+=dfs(k+1,r,d+1);
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        int ans=dfs(0,n-1,1);
        printf("%d\n",ans);
    }
    return 0;
}

图像

整型1只有32位，用来左移会导致整型溢出，用长整型1LL，避免溢出
还有这个题，读题都读了十多分钟，这个分形第一次做真看不出来::>_<::

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<stdio.h>
typedef long long ll;
ll x ,y ;

void dfs(ll n,ll k){
	if(n==0){
		x++,y++;
	}else{
		ll m=n-1,w=1LL<<m,size=1LL<<(m<<1LL);
		if(k<=size){
			dfs(n-1,k);
		}
		else if(k<=2*size){
			y+=w;
			dfs(n-1,k-size);
		}else if(k<=3*size){
			x+=w;
			dfs(n-1,k-2*size);
		}else{
			x+=w,y+=w;
			dfs(n-1,k-3*size);
		}
	}
}

int main()
{
	ll T;
	scanf("%lld",&T);
	while(T--){
		ll k,n;
		scanf("%lld",&k);
		for(n=0;k>(1LL<<(n<<1LL));n++);
		x=y=0;
		dfs(n,k);
		printf("%lld %lld\n",x,y);
	}
	return 0;
}

Wave

这个记忆化搜索，可以理解为从最底层开始，按照中前后序遍历，标记节点，逐层向上递归
时间复杂度是O(N^2),和下面的dp正好是一样的思路
Code 1 (Memoization Depth-First Search)

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
#include <stdio.h>
#include <string.h>
typedef long long ll;
#define N 50

ll dp[N * 2][N * 2];

ll dfs(ll x, ll y, ll n) {
    if (x > n || x < -n || y > n / 2 || y < -n / 2) return 0;
    if (x == n && y == 0) return 1;
    if (dp[x + N][y + N] != -1) return dp[x + N][y + N];
    ll ans = 0;
    ans += dfs(x + 1, y, n);
    ans += dfs(x + 1, y - 1, n);
    ans += dfs(x + 1, y + 1, n); 
    dp[x + N][y + N] = ans; 
    return ans;
}

signed main() {
    ll T;
    scanf("%lld", &T);
    while (T--) {
        ll n;
        scanf("%lld", &n);
        memset(dp, -1, sizeof(dp));
        printf("%lld\n", dfs(0, 0, n));
    }
    return 0;
}

Code 2 (Dynamic Programming)

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
#include <stdio.h>
#include <string.h>

#define N 50
long long dp[N * 2][N * 2];

signed main() {
    long long T;
    scanf("%lld", &T);
    while (T--) {
        long long n;
        scanf("%lld", &n);
        memset(dp, 0, sizeof(dp));
        dp[n + N][0 + N] = 1;
        for (long long x = n - 1; x >= 0; x--) {
            for (long long y = -n / 2; y <= n / 2; y++) {
                dp[x + N][y + N] += dp[x + 1 + N][y + N];
                dp[x + N][y + N] += dp[x + 1 + N][y - 1 + N];
                dp[x + N][y + N] += dp[x + 1 + N][y + 1 + N];
            }
        }
        printf("%lld\n", dp[0 + N][0 + N]);
    }
    return 0;
}

彩球

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
#include <stdio.h>
#include <stdlib.h>
#define N 10010
typedef long long ll;

ll a[N], c[N];

int cmp(const void *x, const void *y) {
    return *(ll *)x - *(ll *)y;
}

ll C(ll i, ll n) {
    if (i < n) return 0;
    if (n == 3) return i * (i - 1) * (i - 2) / 6;
    if (n == 2) return i * (i - 1) / 2;
    return -1;
}

void cnt(ll n, ll *idx, ll *t0, ll *t1) {
    *idx=*t0=*t1=0;
    for (ll i = 1; i < n; i++) {
        if (a[i] != a[i - 1]) {
            if (*idx != 0) *t1 = *t0;
            *t0 = i;
            (*idx)++;
            c[*idx] = *t0 - *t1;
            if (*idx == 1) *t1 = i;
        }
    }
    c[++(*idx)] = n - *t0;
}

ll calc(ll n, ll idx) {
    ll s = 0;
    for (ll i = 1; i <= idx; i++) {
        s += C(c[i], 3);
    }
    for (ll i = 1; i <= idx; i++) {
        s += C(c[i], 2) * (n - c[i]);
    }
    return C(n, 3) - s;
}

int main() {
    ll T;
    scanf("%lld", &T);
    while (T--) {
        ll n, idx, t0, t1;
        scanf("%lld", &n);
        for (ll i = 0; i < n; i++) {
            scanf("%lld", &a[i]);
        }
        qsort(a, n, sizeof(ll), cmp);
        cnt(n, &idx, &t0, &t1);
        ll ans = calc(n, idx);
        printf("%lld\n", ans);
    }
    return 0;
}

冰墩墩与颜色

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
#include<stdio.h>
typedef long long ll;
const ll mod=1e9+7;

ll binpow(ll a,ll n,ll m){
    a%=m;
    ll res=1;
    while(n){
        if(n&1) res=res*a%m;
        a=a*a%m;
        n>>=1;
    }
    return res;
}

int main()
{
    ll T;
    scanf("%lld",&T);
    while(T--){
        ll n;
        scanf("%lld",&n);
        ll ans=((3*binpow(2,n-2,mod)%mod)*(n-1))%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

红球与白球

我的思路是偶然间发现的，这才是正统的(?)
image

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
#include<stdio.h>
typedef long long ll;
const ll mod=1e9+7;
#define N 100010
ll fi[N];

void init(){
    fi[0]=fi[1]=1;
    for(ll i=1;i<N;i++){
        fi[i]=(fi[i-1]+fi[i-2])%mod;
    }
}

ll solve(ll n){
    ll sum=0;
    for(ll i=n-2;i>=0;i--){
        sum=(sum+fi[i]*fi[n-2-i])%mod;
    }
    return sum%mod;
}

int main()
{
    ll T;
    init();
    scanf("%lld",&T);
    while(T--){
        ll n;
        scanf("%lld",&n);
        printf("%lld\n",solve(n));
    }
    return 0;
}

瓷片

这个题，给第一次写正经的dp题的我不小的冲击。。。。
这个状态转移方程太抽象了，第一次看到根本想不到
image

Blocks & Blocks II & Blocks III

美妙的dp题,说句题外话，查阅题解时在csdn看到第一种最简单的dp，嗯嗯，这人写的代码太tm丑了，莫名其妙的逻辑，边缘细节处理也是依托，还喜欢装吊子，看的我直恶心

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
#include <stdio.h>
ll dp1[120][20][150],n=100,m=10,f[11];

void init1(){
    for(int i=1;i<=n;i++){
        dp1[i][1][i]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=1;k<=i;k++){
                for(int s=1;s<k;s++){
                    dp1[i][j][k]+=dp1[i-k][j-1][s];
                }
            }
        }
    }
}

void init2(){
    int i,j,k;
    dp2[0][0]=1;
    for(k=1;k<=n;k++){
        for(j=m;j>0;j--){
            for(i=n;i>=k;i--){
                dp2[j][i]+=dp2[j-1][i-k];
            }
        }
    }
}

void init3(){
    dp2[0][0]=1;
    for(int j=1;j<=m;j++){
        for(int i=j*(j+1)/2;i<=n;i++){
            dp2[j][i]=dp2[j-1][i-j]+dp2[j][i-j];
        }
    }
}

ll fac(ll n){
    f[0]=1;
    for(int i=1;i<=n;i++) f[i]=f[i-1]*i;
    return f[n];
}

int main()
{
    int k;
    /* -------case1------ */
    /* init1(); */
    /* -------case2------ */
    /* init2(); */
    /* -------case3------ */
    /* init3(); */
    /* --------end------- */
    scanf("%d",&k);
    while(k--)
    {
        int n,m,sum=0;
        scanf("%d%d",&n,&m);
        /* ------Blocks------ */
        /* --------out1-------- */
        /* for(int i=1;i<=n;i++){
            sum+=dp1[n][m][i];
        }
        printf("%d\n",sum); */
        /* ------out2 and out3------ */
       /*  printf("%d\n",dp2[m][n]); */
        /* ------Blocks II------ */
        /* sum=sum*((1<<(m-1))-2); */
        /* ------Blocks III------ */
        /* sum=sum*fac(m); */
        /* ----------end---------- */
    }
    return 0;
}

矩阵快速幂

板子题就比较简单了

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
#include<stdio.h>
#include<string.h>
typedef long long ll;
typedef ll Ma[3][3];
const ll mod =1e9+7;

void mul(Ma a,Ma b){
    Ma c;
    memset(c,0,sizeof(c));
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                c[i][j]+=a[i][k]*b[k][j]%mod;
                c[i][j]%=mod;
            }
        }
    }
    memcpy(a,c,sizeof(c));
}

void binpow(Ma a,int n){
    Ma ans={{1,0,0},{0,1,0},{0,0,1}},k;
    memcpy(k,a,sizeof(k));
    while(n){
        if(n&1) mul(ans,k);
        mul(k,k);
        n>>=1;
    }
    memcpy(a,ans,sizeof(ans));
}

ll cal(int n){
    if(n==-1) return 1;
    Ma a={{1,1,0},{1,0,0},{1,0,1}};
    binpow(a,n);
    return (a[0][0]+a[1][0]+a[2][0])%mod;
}

int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%lld\n",cal(n-1));
    }
    return 0;
}
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
#include<stdio.h>
#include<string.h>
typedef long long ll;
typedef ll Ma[2][2];
const ll mod =1e9+7;

void mul(Ma a,Ma b){
    Ma c;
    memset(c,0,sizeof(c));
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                c[i][j]+=a[i][k]*b[k][j]%mod;
                c[i][j]%=mod;
            }
        }
    }
    memcpy(a,c,sizeof(c));
}

void binpow(Ma a,int n){
    Ma ans={{1,0},{0,1}},k;
    memcpy(k,a,sizeof(k));
    while(n){
        if(n&1) mul(ans,k);
        mul(k,k);
        n>>=1;
    }
    memcpy(a,ans,sizeof(ans));
}

ll cal(int n){
    Ma a={{1,1},{1,0}};
    binpow(a,n);
    return a[0][0]*a[1][0]%mod;
}

int main()
{
    int T,a,b;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&a,&b);
        printf("%lld\n",(cal(b+1)-cal(a)+mod)%mod);
    }
    return 0;
}

完结撒花( •̀ ω •́ )✧

xtuoj
#oj
xtuoj 0x11
http://example.com/2024/12/27/xtuoj-0x11/
Author
Anfsity
Posted on
December 27, 2024
Licensed under