285484026

CCPC-Wannafly Winter Camp Day7 Div2
迷宫题解:将每个深度对应的点,加入优先队列以深度从小到大排序,同时用一个变量tmp来记录让当前点前面的点都走出去要...
扫描右侧二维码阅读全文
29
2019/01

CCPC-Wannafly Winter Camp Day7 Div2

迷宫
题解:将每个深度对应的点,加入优先队列以深度从小到大排序,同时用一个变量tmp来记录让当前点前面的点都走出去要用的时间,如果tmp小于当前点的深度,显然tmp应该等于当前点的深度,否则tmp++,因为这个点用去tmp的时间已经走到1节点,所以只要用1的时间来走出去

#include <bits/stdc++.h>

const int MAXN = 1000000;

using namespace std;

int deep[MAXN],Min,Max,ans;
bool ues[MAXN];

vector<int>E[MAXN];

int n;

priority_queue<int>Q;

void dfs(int x){
    
    for(int i = 0;i < E[x].size();i++){
        int v = E[x][i];
        if(!deep[v]){
            deep[v] = deep[x] + 1;        
            
            dfs(v);
        }
    }
    
}

int main()
{
    scanf("%d",&n);Min = n;
    
    for(int i = 1;i <= n;i++){
        scanf("%d",&ues[i]);
    }
    
    int u,v;
    
    for(int i = 1;i < n;i++){
        scanf("%d %d",&u,&v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    deep[1] = 1;
    dfs(1);
    
    for(int i = 1;i <= n;i++){
        deep[i]--;
        if(ues[i]) Q.push(-deep[i]);
    }
        
    
    while(!Q.empty())
    {
        u = Q.top();Q.pop();
        u = -u;
        if(ans < u)
        {
            ans = u;
        }
        else {
            ans++;
        }
    }
    
    printf("%d\n",ans);
    
    return 0;
}

斐波那契数列
题解:
$$\large \sum_{n=1}^{R}(Fib_{n}\&(Fib_{n}-1))=\sum_{n=1}^{R}(Fib_{n}-lowbit(Fib_{n}))$$
$$\large \because \sum_{n=1}^{R}Fib_{n}=Fib_{n+2}-1$$
$$\large \therefore \sum_{n=1}^{R}(Fib_{n}-lowbit(Fib_{n}))=Fib_{n+2}-1-\sum_{n=1}^{R}lowbit(Fib_{n})$$
然后我们打个表发现$\large lowbit(Fib_{n})$是服从下面循环的一个类周期函数

Fib[1+6*T]=1 Fib[2+6*T]=1  Fib[3+6*T]=2
Fib[4+6*T]=1 Fib[5+6*T]=1  Fib[6+6*T]=lowbit(8*(T+1))
#include <bits/stdc++.h>

const long long MOD = 998244353;

using namespace std;

int T;
long long n,cnt,ans;

struct Mat{
    long long d[3][3];
    
    inline void init(){
        for(int i = 1;i <= 2;i++)
            for(int j = 1;j <= 2;j++)
                this->d[i][j] = 0;
    }
    
    friend Mat operator * (const Mat &A,const Mat &B){
        Mat tmp;
        for(int i = 1;i <= 2;i++){
            for(int j = 1;j <= 2;j++){
                tmp.d[i][j] = 0; 
                for(int k = 1;k <= 2;k++){
                    tmp.d[i][j] += (A.d[i][k] * B.d[k][j]) % MOD;
                    tmp.d[i][j] %= MOD;
                }                    
            }        
        }
        return tmp;
    }
    
}Mat_ans,Mat_res;

long long solve(long long x,long long base){
    if(x <= 0) return 0;
    return (base*(x - x / 2)% MOD + solve(x / 2,base*2%MOD)% MOD) % MOD;
}

inline long long fib(long long x)
{
    Mat_ans.init();Mat_res.init();
    
    Mat_ans.d[1][4] = Mat_ans.d[2][5] = 1;
    Mat_res.d[1][6] = Mat_res.d[1][7] = Mat_res.d[2][8] = 1;    
    
    while(x){
        if(x&1) Mat_ans =  Mat_ans * Mat_res;
        Mat_res = Mat_res * Mat_res;
        x >>= 1;
        
    }
    
    long long tmp = 0;
    
    tmp = Mat_ans.d[1][9] + Mat_ans.d[1][10];
    tmp %= MOD;
    
    return tmp;
}

inline void solve()
{
    cnt = n / 6;ans = 0;
    
    switch(n - 6 * cnt){
        case 1 : ans += 1;break;
        case 2 : ans += 2;break;
        case 3 : ans += 4;break;
        case 4 : ans += 5;break;
        case 5 : ans += 6;break;
    }
    
    ans %= MOD;
    ans += solve(cnt,8);
    ans %= MOD;
    
    ans += (cnt%MOD*6)%MOD;
    ans %= MOD;
    
    ans %= MOD;ans += MOD;ans %= MOD;
    
    ans *= -1;
    
    ans += fib(n) - 1;
    
    ans %= MOD;ans += MOD;ans %= MOD;
    
}

int main()
{
    scanf("%d",&T);

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

抢红包机器人
题解:队友写的,占坑

#include<bits/stdc++.h>

using namespace std;
const int N = 105;
int a[N][N];
int f[N][N];
int n,m;
set<int>tot[N];
int ans[N];
set<int>t[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d",&a[i][0]);
        for(int j=1;j<=a[i][0];++j){
            scanf("%d",&a[i][j]);
        }
        for(int j=a[i][0];j>=1;--j){
            for(int k=j-1;k>=1;--k){
                tot[a[i][j]].insert(a[i][k]);
            }
        }
    }
    for(int i=1;i<=n;++i){
        t[i].insert(i);
        for(std::set<int>::iterator j=tot[i].begin();j!=tot[i].end();++j){
            t[i].insert(*j);
            for(std::set<int>::iterator k = tot[*j].begin();k!=tot[*j].end();++k){
                t[i].insert(*k);
            }
        }
    }
    int minn = 147483647;
    for(int i=1;i<=n;++i){
        int temp = t[i].size();
        if(temp<minn)minn = temp;
    }
    printf("%d",minn);
    return 0;
}

强壮的排列
题解:和CCPC-Wannafly Winter Camp Day4 Div2的置置置换想法是一样的,在那道题目的基础上加上滚动数组就可以打个表。然后就过了,因为是打的表挂程序就没有意义了,我就挂个那个前几天的题解吧
置置置换

Last modification:January 29th, 2019 at 04:15 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment