4.7-4.9补题+水题+高维前缀和

题目链接：51nod 1718 Cos的多项式 【数学】

题解：

2cosx=2cosx

2cos2x=(2cosx)^2-2

2cos3x=(2cosx)^3-3*(2cosx)

数归证明2cos(nx)能表示成关于2cosx的多项式,设为f(n)

f(1)=x,f(2)=x^2-2(其中的x就是2cosx)

假设n=1~k时均成立(k>=3)

当n=k+1时

由cos((k+1)x)=cos(kx)cos(x)-sin(kx)sin(x)

cos((k-1)x)=cos(kx)cos(x)+sin(kx)sin(x)

相加得到cos((k+1)x)+cos((k-1)x)=cos(kx)*2cos(x)

从而f(k+1)+f(k-1)=f(k)*x

-> f(k+1)=f(k)*x-f(k-1)

从而成立

这是我们根据递推关系可知对于项的系数和也满足这个关系式

g(1)=1,g(2)=-1.....于是求这个数列的通项即可。

然后求出循环节：1, -1, -2, -1, 1, 2……

//yy：我第一遍看这题没看懂题目表达的意思。。。傻傻

#include<cstdio>using namespace std;

typedef long long ll;

int a[6] = {1, -1, -2, -1, 1, 2};
int main() {
    ll x;
    scanf("%lld", &x);
    printf("%d
", a[(x-1) % 6]);
    return 0;
}

--------------------------------------------------------------------------------------------------------------------

又做了一遍几道以前做过的水题，卖萌。。。

poj1611 The Suspects 【并查集】

题意：有N个学生，编号为0-N-1，现在0号学生感染了非典，凡是和0在一个社团的人就会感染，并且这些人如果还参加了别的社团，他所在的社团照样全部感染，求感染的人数。

题解：求0号所在的强连通图的结点数。并查集。

我的：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<cmath>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;

const int N = 30005;
int n, m;
int fa[N], rk[N];

void init() {
    for(int i = 0; i < n; ++i) {
        fa[i] = i;
        rk[i] = 1;
    }
}
int fin(int x) {
    if(fa[x] != x) fa[x] = fin(fa[x]);
    return fa[x];
}
void join(int x, int y) {
    if((x = fin(x)) == (y = fin(y))) return;
    fa[x] = y;
    rk[y] += rk[x];//第一遍手残写成rk[y]++
}

int main () {
    int i, j, x, y, cnt, ans;
    while(~scanf("%d%d", &n, &m), n || m) {
        init();
        for(i = 0; i < m; ++i) {
            scanf("%d", &cnt);
            scanf("%d", &x);
            for(j = 1; j < cnt; ++j) {
                scanf("%d", &y);
                join(x, y);
            }
        }
        ans = rk[fin(0)];
        printf("%d
", ans);
    }
    return 0;
}

学弟的代码WA了，然后把判断父节点还是找根那里给他改对了。。。：

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int pre[30005];
int visit[30005];
int find(int xxx)
{
    if(xxx!=pre[xxx])
    return pre[xxx]=find(pre[xxx]);
    else
    return xxx;
}
void join(int ax,int bx)
{
    int axx=find(ax);
    int bxx=find(bx);
    if(axx!=bxx)
    pre[bxx]=axx;
}
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m)&&n+m)
    {
        int i,j;
        for(i=0;i<n;i++)
            pre[i]=i;
        memset(visit,0,sizeof(visit));
        visit[0]=1;
        int ans=1;
        for(i=1;i<=m;i++)
        {
            int x;
            scanf("%d",&x);
            int q[30005];
            bool f=false;
            for(j=0;j<x;j++)
            {
                scanf("%d",&q[j]);
                if(find(q[j])==0)
                f=true;
            }
            if(f)
            {
                for(j=0;j<x;j++)
                {
                    join(0,q[j]);
                }
            }
            else
            {
                for(j=1;j<x;j++)
                {
                    join(q[0],q[j]);
                }
            }
        }
        for(i=1;i<n;i++)
        {
            if(find(i)==0)
            ans++;
        }
        printf("%d
",ans);
    }
    return 0;
}

hdu1878 欧拉回路【并查集判连通或 dfs判连通】

并查集判连通，然后判断欧拉回路：无向图度数为偶

方法一：并查集

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<cmath>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;

const int N = 1005;
int fa[N];
int n, m;
int cnt;
int du[N];

int fin(int x) {
    if(fa[x] != x) fa[x] = fin(fa[x]);
    return fa[x];//第一遍写成返回x,心塞，我好蠢啊。。。
}
void join(int x, int y) {
    if((x = fin(x)) == (y = fin(y))) return ;
    else { fa[x] = y; cnt++; }
}

int main () {
    int x, y, i ,j;
    while(scanf("%d", &n), n) {
        CLR(du, 0);
        for(i = 1; i <= n; ++i) fa[i] = i;
        cnt = 0;

        scanf("%d", &m);
        int f = 0;
        while(m--) {
            scanf("%d%d", &x, &y);
            join(x, y);
            du[x]++;  du[y]++;
        }
        if(cnt == n-1) {
            for(i = 1; i <= n; ++i) {
                if(du[i] % 2 == 1) {
                    f = 1; break;
                }
            }
            if(f) printf("0
");
            else printf("1
");
        }
        else printf("0
");
    }
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<cmath>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;

const int N = 1005;
int fa[N];
int n, m;
int cnt;
int du[N];

int fin(int x) {
    if(fa[x] != x) fa[x] = fin(fa[x]);
    return fa[x];
}
void join(int x, int y) {
    if((x = fin(x)) == (y = fin(y))) return ;
    else { fa[x] = y; }
}

int main () {
    int x, y, i ,j;
    while(scanf("%d", &n), n) {
        CLR(du, 0);
        for(i = 1; i <= n; ++i) fa[i] = i;
        cnt = 0;

        scanf("%d", &m);
        int f = 0;
        while(m--) {
            scanf("%d%d", &x, &y);
            join(x, y);
            du[x]++;  du[y]++;
        }
        for(i = 1; i <= n; ++i) {
            if(fa[i] == i) cnt++;
            if(du[i] % 2 == 1) {
                f = 1; break;
            }
        }
        if(f || cnt != 1) printf("0
");
        else printf("1
");
    }
    return 0;
}

方法二：dfs

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<cmath>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;

const int N = 1005;
int n, m;
int du[N];
int g[N][N], vis[N];

void dfs(int x) {
    vis[x] = 1;
    for(int i = 1; i <= n; ++i) {
        if(!vis[i] && g[x][i])
            dfs(i);
    }
}

int main () {
    int x, y, i ,j;
    while(scanf("%d", &n), n) {
        CLR(du, 0);
        CLR(vis, 0);
        CLR(g, 0);

        scanf("%d", &m);
        int f = 0;
        while(m--) {
            scanf("%d%d", &x, &y);
            g[x][y] = g[y][x] = 1;
            du[x]++;  du[y]++;
        }
        dfs(1);
        for(i = 1; i <= n; ++i) {
            if(!vis[i] || du[i] % 2 == 1) {
                f = 1; break;
            }
        }
        if(f) printf("0
");
        else printf("1
");
    }
    return 0;
}

//yy:记得上回去比赛纠结死在格式错误上，水题各种格式错误，回来后改，有一题把string全部改成char就过了，我现在也不知道哪里错了。。。不贴它了，气哭了。。。

题目链接:L1-039. 古风排版 [水题]

//yy：WA的郁闷,姿势太差……

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<limits.h>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long ll;
char s[1005], ans[105][1005];
int main() {
    int i, j, len, row, col, r, c;
    scanf("%d ", &row);
    gets(s);
    len = strlen(s);
    /*WA了。。
    int t = len % row;
    col = len / row + t;
    */
    col = len / row + (len % row == 0 ? 0 : 1);
    for(i = 0; i < row; ++i) {//唉，别漏了啊。。。
        ans[i][0] = ' ';//orz
        ans[i][col] = '

4.7-4.9补题+水题+高维前缀和

相关推荐