分类目录归档：数学

CSP 202006-4 1246

发表评论

48分题解：|S|=1
推导：
1->2
2->4
4->{1,6}
6->{6,4}
则有：
a1’=a4
a2’=a1
a4’=a2+a6
a6’=a4+a6
矩阵快速幂：
\begin{bmatrix}
a_{1}^{\prime} \\
a_{2}^{\prime} \\
a_{4}^{\prime} \\
a_{6}^{\prime}
\end{bmatrix} =
\begin{bmatrix}
a_4 \\
a_1 \\
a_2 + a_6 \\
a_4 + a_6
\end{bmatrix} =
\begin{bmatrix}
0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1
\end{bmatrix} *
\begin{bmatrix}
a_1 \\
a_2 \\
a_4 \\
a_6
\end{bmatrix}

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 <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

const long long MOD = 998244353;
const int maxtrixN = 4;

struct matrix {
    long long arr[maxtrixN][maxtrixN];
    matrix operator * (const matrix& m2) {
        matrix result;
        long long(&arr)[maxtrixN][maxtrixN] = result.arr;
        const long long(&arr1)[maxtrixN][maxtrixN] = this->arr;
        const long long(&arr2)[maxtrixN][maxtrixN] = m2.arr;
        for (int i = 0; i < maxtrixN; i++) {
            for (int j = 0; j < maxtrixN; j++) {
                arr[i][j] = 0;
                for (int k = 0; k < maxtrixN; k++) {
                    arr[i][j] += arr1[i][k] * arr2[k][j] % MOD;
                    arr[i][j] += MOD;
                    arr[i][j] %= MOD;
                }
            }
        }
        return result;
    }
};
const matrix c = { 0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,1 };
matrix quickpow(long long n) {
    if (n == 1)return c;
    matrix half = quickpow(n / 2);
    matrix result = half * half;
    if (n & 1)result = result * c;
    return result;
}
long long getResult(long long n, int index){
    matrix re=quickpow(n);
    return re.arr[index][0] % MOD;
}
int main() {
    ios::sync_with_stdio(false);
    long long n, s;
    cin>>n>>s;
    if(n==0){
        if(s==1){
            cout<<"1";
        }else{
            cout<<"0";
        }
    }else if(s==1){
        cout<<getResult(n, 0);
    }else if(s==2){
        cout<<getResult(n, 1);
    }else if(s==4){
        cout<<getResult(n, 2);
    }else if(s==6){
        cout<<getResult(n, 3);
    }
}

待完善96分题解。

CSP 202012-2 期末预测之最佳阈值

1条回复

这题也不知道咋回事，我想了个异想天开的做法，也不知道行不行，交上去竟然过了！哈哈哈哈哈哈。
暴力的N^2做法可以得70，我写个异想天开的排序+前缀和做法100。
感觉有必要写个题解，在这里写一下。

本题的大致意思是，给出一堆人的学习努力程度（用一个非负整数表示）和其是否挂科（并不必然成正相关，其中可能混杂学习努力程度高的人也挂科的情况）。要求找到一个学习努力程度基准分数，使得用该基准评判学生的努力程度时，判断对的最多。

我主要利用差分的思想进行解题。对于一个分数，我们其实只需要知道通过与挂科的人数的差值即可。基准分数是否应该低于或高于某一特定学习努力程度分数，在于其能否为总人数作出贡献。例如，如果一个分数有3人通过，3人挂科，则不管选择比他低的基准还是比他高的基准，则都对总的人数做出了3的贡献，可以相互抵消。但若4人通过，3人挂科，则更应该优先选择比其低的基准，因为这样的话，判断对的就多了一个。

首先建立一个map对输入的数据进行排序。由于选择指标的时候只看努力程度不看人，因此可以将同努力程度的人们聚合起来。如果该人挂科，在是否通过的数组cnt里-1，如果通过则+1.这样就产生了一个差分的数组cnt。此时，该数组cnt表示的是在选定该分数作为基准后，通过的人比挂科的人多多少。

然后，对其进行前缀和操作。借助前缀和，我们可以得到数组presum，可以计算选择任意基准分数时，通过的人比挂科的人多多少。还可计算选择任意基准分数时，挂科的人比通过的人多多少（通过对计算值取负）。这样，我们分别计算高于基准分数通过的人比挂科的人多多少，和低于基准分数时挂科的人比通过的人多多少。将他们相加，就可以得到一个判断正确的人数的差分。统计这些差分的最大值，就可以算出对应的基准分数。

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
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>

using namespace std;

int m;
map<int, int> stat;
int arrSize = 0;
int y[100005], cnt[100005], presum[100005];

int main() {
    ios::sync_with_stdio(false);
    cin >> m;
    while (m--) {
        int y, result;
        cin >> y >> result;
        stat[y] += result ? 1 : -1;
    }
    for (auto iter = stat.begin(); iter != stat.end(); iter++) {
        int ind = iter->first, v = iter->second;
        y[arrSize] = ind;
        cnt[arrSize] = v;
        arrSize++;
    }
    presum[0]=cnt[0];
    for(int i=1;i<arrSize;i++){
        presum[i]=presum[i-1]+cnt[i];
    }
    int index=0, cmpValue=presum[arrSize-1];
    for(int i=1;i<arrSize;i++){
        int tmpV=presum[arrSize-1]-presum[i-1]*2;
        if(tmpV>=cmpValue){
            cmpValue=tmpV;
            index=i;
        }
    }
    cout<<y[index];
}

Openjudge 打印月历

发表评论

http://noi.openjudge.cn/ch0113/24/

描述
给定年月，打印当月的月历表。

输入
输入为一行两个整数，第一个整数是年份year（1900 ≤ year ≤ 2099），第二个整数是月份month（1 ≤ month ≤ 12），中间用单个空格隔开。

输出
输出为月历表。月历表第一行为星期表头，如下所示：
Sun Mon Tue Wed Thu Fri Sat
其余各行一次是当月各天的日期，从1日开始到31日（30日或28日）。
日期数字应于星期表头右对齐，即各位数与星期表头相应缩写的最后一个字母对齐。日期中间用空格分隔出空白。

样例输入

1
2006 5

样例输出

1
2
3
4
5
6
Sun Mon Tue Wed Thu Fri Sat
      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

提示
闰年判断方法：能被4整除但不能被100整除，或者能被400整除。
1900年1月1日是周一。
继续阅读 →

Codeforces 102346 problem K Keep Calm and Sell Balloons

发表评论

这道题重点要说矩阵快速幂，公式不会推。用了一个Berlekamp-Massey algorithm的模板。最主要想将一般情况下线性递推式怎么用矩阵快速幂优化。
本题目的递推公式是：F(n)=6*F(n-1)-8*F(n-2)-8*F(n-3)+16*F(n-4)。
故构造矩阵递推公式：
\begin{bmatrix}
F(n) \\
F(n-1) \\
F(n-2) \\
F(n-3)
\end{bmatrix} =
\begin{bmatrix}
6 & -8 & -8 & 16 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix} *
\begin{bmatrix}
F(n-1) \\
F(n-2) \\
F(n-3) \\
F(n-4)
\end{bmatrix}
得
\begin{bmatrix}
F(n) \\
F(n-1) \\
F(n-2) \\
F(n-3)
\end{bmatrix} =
\begin{bmatrix}
6 & -8 & -8 & 16 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}^{n-4} *
\begin{bmatrix}
F(4) \\
F(3) \\
F(2) \\
F(1)
\end{bmatrix}
。
对于一般的线性递推公式F(n)=a_1*F(n-1)+a_2*F(n-2)+…+a_{k-1}*F(n-k+1)+a_k*F(n-k)，
可以构造一长宽都为k的矩阵，满足：
\begin{bmatrix}
F(n) \\
F(n-1) \\
… \\
F(n-k+2) \\
F(n-k+1)
\end{bmatrix} =
\begin{bmatrix}
a_1 & a_2 & … & a_{n-k+1} & a_{n-k} \\
1 & 0 & … & 0 & 0 \\
0 & 1 & … & 0 & 0 \\
… & … & … & … & … \\
0 & 0 & … & 1 & 0
\end{bmatrix} *
\begin{bmatrix}
F(n-1) \\
F(n-2) \\
… \\
F(n-k+1) \\
F(n-k)
\end{bmatrix}
因此只需对该矩阵做快速幂，即可以以O(k^3logn)的复杂度推出任意n情况下的数列的值。
本题代码如下：

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 <iostream>
using namespace std;
const long long MOD = 1e9 + 7;
const int maxtrixN=4;
struct matrix {
    long long arr[maxtrixN][maxtrixN];
    matrix operator * (matrix m2) {
        matrix result;
        long long(&arr)[maxtrixN][maxtrixN] = result.arr;
        const long long(&arr1)[maxtrixN][maxtrixN] = this->arr;
        const long long(&arr2)[maxtrixN][maxtrixN] = m2.arr;
        for (int i = 0; i < maxtrixN; i++) {
            for (int j = 0; j < maxtrixN; j++) {
                arr[i][j] = 0;
                for (int k = 0; k < maxtrixN; k++) {
                    arr[i][j] += arr1[i][k] * arr2[k][j] % MOD;
                    arr[i][j] += MOD;
                    arr[i][j] %= MOD;
                }
            }
        }
        return result;
    }
};
const matrix c = { 6,-8,-8,16,1,0,0,0,0,1,0,0,0,0,1,0 };
matrix quickpow(long long n) {
    if (n == 1)return c;
    matrix half = quickpow(n / 2);
    matrix result = half * half;
    if (n & 1)result = result * c;
    return result;
}
long long getValue(long long n) {
    matrix result = quickpow(n);
    long long(&arr)[4][4] = result.arr;
    return (arr[0][0] * 1536 % MOD + arr[0][1] * 416 % MOD + arr[0][2] * 96 % MOD + arr[0][3] * 24 % MOD +MOD) % MOD;
}
int main() {
    int n;
    long long a1[] = { 0,2,24,96,416,1536 };
    cin >> n;
    if (n < 6)cout << a1[n];
    else cout << getValue(n-5);
}

计蒜客 Random Access Iterator

发表评论

原题链接：https://nanti.jisuanke.com/t/41392
竟然做出来一道这么复杂的概率+DFS+逆元题，开心到爆炸，特此发题解一篇^v^

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#define MOD 1000000007
#define ll long long
using namespace std;
int n;
int MDep;
vector<int> edges[1000005];
bool visited[1000005];
ll quickpow(ll a, ll b) {
    if (b == 0)return 1;
    ll re = quickpow(a, b / 2) % MOD;
    re = (re * re) % MOD;
    if (b % 2 == 1)re *= a % MOD;
    return re % MOD;
}
inline ll inv(ll x) {
    return quickpow(x, MOD - 2) % MOD;
}
inline ll chance1(ll TotNode) {
    ll ch = (inv(TotNode)) % MOD;
    return ch;
}
inline ll chance2(ll onceCh,ll TotNode) {
    ll onceNonch = (1ll-onceCh+MOD) % MOD;
    ll nonch = quickpow(onceNonch, TotNode);
    ll fin = (1ll - nonch + MOD) % MOD;
    return fin;
}
int dfsMaxDep(int node) {
    int maxDep = 1;
    bool hasChild = false;
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (visited[edges[node][i]])continue;
        hasChild = true;
        maxDep = max(maxDep, dfsMaxDep(edges[node][i]) + 1);
    }
    return maxDep;
}
ll dfsChance(int depth,int node){
    if (depth == MDep)return 1;
    ll ch = 0,sCh=chance1(node==1?edges[node].size(): edges[node].size()-1);
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (visited[edges[node][i]])continue;
        ll CurCH = dfsChance(depth + 1, edges[node][i]);
        if (CurCH) {
            ch += (CurCH * sCh) % MOD;
            ch %= MOD;
        }
    }
    return chance2(ch, node == 1 ? edges[node].size() : edges[node].size() - 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    MDep = dfsMaxDep(1);
    memset(visited, false, sizeof(visited));
    ll ch = dfsChance(1, 1);
    cout << ch;
}

洛谷 P2320 [HNOI2006]鬼谷子的钱袋

发表评论

想不出来：参考题解：
https://www.luogu.org/blog/user50514/solution-p2320
https://www.luogu.org/blog/user26625/solution-p2320

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll ans,n,z[70];
int main(){
    cin>>n;
    while(n){
        z[++ans]=(n+1)/2;
        n/=2;
    }
    sort(z+1,z+ans+1);
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++)cout<<z[i]<<" ";
}

洛谷 P2261 [CQOI2007]余数求和

发表评论

新学的知识点：除法分块。
题解：https://www.luogu.org/blog/Capella/solution-p2261

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#define ll long long
using namespace std;
ll n,k,ans;
int main(){
    cin>>n>>k;
    for(ll l=1,t,r;l<=n;l=r+1){
        t=k/l;
        if(t==0)r=n;
        else r=min(k/t,n);
        ans-=t*(l+r)*(r-l+1)/2;
    }
    cout<<ans+n*k;
}

洛谷 P2327 [SCOI2005]扫雷

发表评论

还以为是搜索，写了半天之后懒得写了看看题解才发现出问题了。。
题解：https://www.luogu.org/blog/user31898/solution-p2327

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstring>
using namespace std;
int n;
int arr1[10005],arr2[10005];
bool f(){
    for(int i=2;i<=n+1;i++){
        arr2[i]=arr1[i-1]-arr2[i-1]-arr2[i-2];
        if(arr2[i]!=1&&arr2[i]!=0)return false;
        if(i==n+1&&arr2[i]!=0)return false;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>arr1[i];
    int num=0;
    arr2[1]=0;
    if(f())num++;
    arr2[1]=1;
    if(f())num++;
    cout<<num;
}

洛谷 P1984 [SDOI2008]烧水问题

发表评论

有意思的一道数学题，就是找规律嘛。

1
2
3
4
5
6
7
8
9
10
11
#include<cstdio>
using namespace std;
int main(){
    double v=420000;
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        v*=1.0*(2*i-1)/2/i;
    }
    printf("%.2lf",v);
}