This is my blog.
应该网络赛已结束就写点什么的，现在都忘记的差不多了。明明照旧没来，两人一队真的有点忙。庆幸的是比昨天的那场好太多了，这次AC了四题，我和博博都很兴奋。尤其最后一题，是结束之前交的。由于“随机大法”的存在，我们吃完饭后，才发现又AC一题了。我还兴奋的有两件事，一件就是原来还可以随机大法这么干啊！第二件则是，我居然做出了AC率低的题目，难道是因为都去随机了吗？总之很开心呢！补题补题！
（未完待续）

A. B.cable cable cable

这题其实仔细想想，so easy！代码也很短。看了一下博博现场的代码，居然一下子就发现了正解。
首先肯定要有k个分开连的，剩下的m-k个是作为替补的。比如在k个中没有选到某个，而选了剩下的那个，而因为没有选到的那个有k种不同的可能，所以需要和k个都连接，才能确保随便选都可以满足k个的存在。
来看神奇的代码吧！

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
    ll m,k;
    while(scanf("%lld %lld",&m,&k)!=EOF){
        printf("%lld\n",(k+(m-k)*k));
    }
    return 0;
}

C. D.card card card

找最长上升和下降子序列。博博提示dp，我想到了逆序对，顺利带偏方向。在最后几分钟，博博说这不是LIS问题吗？晕。终于过。博博加了线段树优化，但我看不懂。就先存着吧。

AC代码

//1.线段树优化
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 1e5 + 5;
struct node{
    int data, L, R;
    struct node * lchild, * rchild;
};
int a[maxn];
bool flag = 1;
void build(int L, int R, node * & tree){
    tree -> L = L;
    tree -> R = R;
    tree -> data = 0;
    if(L == R){
        if(flag)    tree -> lchild = tree -> rchild = NULL;
        return ;
    }
    int mid = (L + R) >> 1;
    if(flag){
        tree -> lchild = (node *) malloc(sizeof(node));
        tree -> rchild = (node *) malloc(sizeof(node));
    }
    build(L, mid, tree -> lchild);
    build(mid + 1, R, tree -> rchild);
}
// " update "
void update(int idx, int now, node * & tree){
    if(tree -> L == tree -> R){
        tree -> data = now;
        return ;
    }
    int mid = (tree -> L + tree -> R ) >> 1;
    if(idx <= mid)  update(idx, now, tree -> lchild);
    if(idx > mid)   update(idx, now, tree -> rchild);
    tree -> data = max(tree -> lchild -> data, tree -> rchild -> data);
}
//" query "
int query(int L, int R, node * & tree){
    if(tree -> L == L && tree -> R == R)    return tree -> data;
    int mid = (tree -> L + tree -> R) >> 1;
    if(R <= mid)    return query(L, R, tree -> lchild);
    else if( L > mid)   return query(L, R, tree -> rchild);
    else    return max(query(L, mid, tree -> lchild), query(mid + 1, R, tree -> rchild));
}
int main(){
    int T;
    scanf("%d", &T);
    node * root = (node *) malloc(sizeof(node));
    build(1, maxn, root);
    flag = 0;
    while(T--){
        //initialization
        int n, k;
        scanf("%d%d", &n, &k);
        int dp[maxn] , temp = 0;
        for(int i = 1; i <= n; i ++ )   {scanf("%d", &a[i]);temp = max(temp, a[i]); }
        build(1, temp, root);
        //perform the algorithm : dp
        for(int i = 1; i <= n; i ++){
            int Max = query(1, a[i], root);
            dp[i] = Max + 1;
            update(a[i], dp[i], root);
        }
        int ans1 = 0;
        for(int i = 1; i <= n; i ++)    ans1 = max(ans1, dp[i]);
        build(1, temp, root);
        for(int i = 1;i  <= n; i ++){
            int Max = query(a[i], temp, root);
            dp[i] = Max + 1;
            update(a[i], dp[i], root);
        }
        int ans2 = 0;
        for(int i = 1; i <= n; i ++)    ans2 = max(ans2, dp[i]);
        int ans = n - max(ans1, ans2);
        //        printf("%d\n", ans);
        if(ans <= k)    printf("A is a magic array.\n");
        else    printf("A is not a magic array.\n");
    }
    return 0;
}
//2.暴力LIS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=1e5+5;
int arr[MAXN],ans[MAXN],len;
int ans1,ans2;
int main(){
    int T,p,k;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&p,&k);
        for(int i=0; i<p; ++i)
            scanf("%d",&arr[i]);
        ans[0] = arr[0];
        len=0;
        for(int i=1; i<p; ++i){
            if(arr[i]>ans[len])
                ans[++len]=arr[i];
            else{
                long long pos;
                pos=lower_bound(ans,ans+len,arr[i])-ans;
                ans[pos] = arr[i];
            }
        }
        ans1=len+1;
			//找最长下降子序列
        for(int i=0;i<p;i++)
            arr[i]*=-1;
        ans[0] = arr[0];
        len=0;
        for(int i=1; i<p; ++i){
            if(arr[i]>ans[len])
                ans[++len]=arr[i];
            else{
                long long pos;
                pos=lower_bound(ans,ans+len,arr[i])-ans;
                ans[pos] = arr[i];
            }
        }
        ans2=len+1;
        int ans=p-max(ans1,ans2);
        if(ans<=k)printf("A is a magic array.\n");
        else    printf("A is not a magic array.\n");
    }
    return 0;
}

E.number number number

思路一（找规律）

在斐波那契数列中任取k个数字，找到一个最小的不能由这k个数字之和表示的n
现场中，我神奇地再次找到了规律，估计运气好吧！照样是手残，博博将其变为矩阵，用了矩阵快速幂的模版，写了代码，AC了！博博的代码写的很好看，很优美。
规律如下：

1	2	3	4	5
1*3-0+1	4*3-1+1	12*3-4+1	33*3-12+1	88*3-33+1

即\(f(k)=f(k-1)*3-f(k-2)+1\)
然后转换成矩阵
icpc22

现场代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
struct Mat{
    int row, col ;
    ll N[25][25];
    Mat(int row = 0 , int col = 0){
        memset(N, 0, sizeof(N));
        this -> row = row;
        this -> col = col;
    }
    Mat operator * (const Mat B) const {
        Mat A(row, B.col);
        for(int i = 0 ;i < row; i ++)
            for(int k = 0 ; k < col; k ++)
                for(int j = 0 ; j < B.col; j++){
                    A.N[i][j] = ( A.N[i][j] + N[i][k] * B.N[k][j] % mod ) % mod;
                }
        return A;
    }
    Mat operator ^ (int x) const {
        Mat A(row,row) , temp = *this;
        for(int i = 0 ; i < row; i ++)  A.N[i][i] = 1;
        while(x){
            if(x & 1)   A = A * temp;
            temp = temp * temp;
            x>>= 1;
        }
        return A;
    }
};
int main(){
    Mat A(3, 3), B(1, 3);
    A.N[0][0] = 3, A.N[0][1] = 1, A.N[1][0] = -1, A.N[1][1] = 0, A.N[2][0] =1, A.N[2][2] = 1;
    B.N[0][0] = 12, B.N[0][1] = 4, B.N[0][2] = 1;
    
    int k;
    while(scanf("%d", &k) != EOF){
        if(k == 1)  printf("4\n");
        else if( k == 2)    printf("12\n");
        else{
            Mat C(1, 3);
            C = B * (A ^ (k - 2));
            printf("%lld\n", (C.N[0][0]% mod + mod ) % mod);
        }
    }
    return 0;
}

思路二（严谨思路）

思路二，还是来自那个dalao的博客
读完之后，觉得很有道理，真的是很扎实。
一个数如果不能被\(k\)个Fibonacci 数之和表示，那么它至少要用\(k+1\)个不同的 Fibonacci 数表示，考虑唯一分解的 Fibonacci 进制，进制下相邻位不能同时为1，能包含\(k+1\)个1的数字至少有\(2k+1\)位，这个数字加一后会变成一个长度为\(2k+2\)的数字，所以它的值是\(Fib_{2k+3}-1\)。
转换为矩阵：
\(\left( \begin{array}{ccc}Fib_k & Fib_{k-1} \end{array} \right)\)
=\(\left( \begin{array}{ccc}Fib_{k-1} & Fib_{k-2} \end{array} \right)*\\\left( \begin{array}{ccc}1 & 1 \\ 1 & 0 \end{array} \right)\)

AC代码

#include <cstdio>
#include <cstring>
typedef long long ll;
const ll mod = 998244353;
struct Mat{
    int row, col ;
    ll N[25][25];
    Mat(int row = 0 , int col = 0){
        memset(N, 0, sizeof(N));
        this -> row = row;
        this -> col = col;
    }
    Mat operator * (const Mat B) const {
        Mat A(row, B.col);
        for(int i = 0 ;i < row; i ++)
            for(int k = 0 ; k < col; k ++)
                for(int j = 0 ; j < B.col; j++){
                    A.N[i][j] = ( A.N[i][j] + N[i][k] * B.N[k][j] % mod ) % mod;
                }
        return A;
    }
    Mat operator ^ (int x) const {
        Mat A(row,row) , temp = *this;
        for(int i = 0 ; i < row; i ++)  A.N[i][i] = 1;
        while(x){
            if(x & 1)   A = A * temp;
            temp = temp * temp;
            x>>= 1;
        }
        return A;
    }
};
int main(){
    Mat A(2,2);
    A.N[0][0]=1;A.N[0][1]=1;A.N[1][0]=1;A.N[1][1]=0;
    int k;
    while(scanf("%d",&k)!=EOF){
        Mat B=A^(2*k+3);
        printf("%lld\n",(B.N[1][0]-1)%mod);
    }
    return 0;
}

F.

G. H.transaction transaction transaction

当时居然把把自己绕晕了，走还是不走，这是个问题啊！本来想用图做的，后来发现万一是个环怎么办？压根儿没有想到可以dp呢！对于要经过这个地方，可以看作，卖掉之前的书，再买一次书。这样只要纠结买不买就可以。然后呢，这里的路是无向图，所以需要二维数组。代码还是简单的。但我居然在看了dp后，不想dp。应该每一题都想想dp的呀！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=2e5+10;
const int maxx=1e5+5;
typedef long long ll;
ll dp[maxn][2],cost[maxx];
struct ty{
    int u,v,cost;
}map[maxn];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i = 1; i <= n; i ++)
            scanf("%lld",&cost[i]);
        int k = 0;
        for(int i = 1; i < n; i ++){
            scanf("%d%d%d",&map[k].u,&map[k].v,&map[k].cost);
            map[k+1].u = map[k].v; map[k+1].v = map[k].u; map[k+1].cost = map[k].cost; k +=2;
        }
        
        memset(dp,0,sizeof(dp));
        for(int i = 0;i < k; i ++){
            dp[map[i].v][0] = max(dp[map[i].v][0],dp[map[i].u][0] - cost[map[i].u] - map[i].cost + cost[map[i].v]);
            dp[map[i].v][1] = max(dp[map[i].v][1],dp[map[i].u][1] - cost[map[i].v] - map[i].cost + cost[map[i].u]);
        }
        
        ll ans = dp[1][0];
        for(int i = 1;i <= n; i ++) for(int j = 0; j < 2; j ++) ans = max(dp[i][j],ans);
        printf("%lld\n",ans);
    }
    return 0;
}

I.

J.

K. L.card card card

不知道为什么这题没什么人做啊！题目中的“MJF also guarantees that the sum of all “penalty value” is exactly equal to the number of all cards.“是关键，所以直接暴力，找到第一个sum不小于0的就可以了。

#include <iostream>
#include <cstdio>
using namespace std;
int a[1000005];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            a[i]-=x;
        }
        int ans=0;int sum=0;
        for(int i=1;i<n;i++){
            sum+=a[i];
            if(sum<0){
                ans=i;
                sum=0;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

后记

转载请注明出处，谢谢。

愿我是你的小太阳

A.

B.cable cable cable

C.

D.card card card

AC代码

E.number number number

思路一 （找规律）

现场代码

思路二 （严谨思路）

AC代码

F.

G.

H.transaction transaction transaction

I.

J.

K.

L.card card card

后记

思路一（找规律）

思路二（严谨思路）