scturtle's 渣代码集散地

c-v 下一页

m-v 上一页

c-l 重绘屏幕，并将光标所在行置于屏幕的中央

c-p c-n c-b c-f 上下左右

m-f m-b 前一词 后一词

c-a c-e 行首 行尾

m-a m-e 句首 句尾

m-< m-> 文章首 文章尾

（c-u 数字参数 | m+数字参数） 命令

C-u 8 C-v 将屏幕向下滚动 8 行

c-g 终止命令

C-x 1   只保留一个窗格

<Delback>    删除光标前的一个字符

C-d          删除光标后的一个字符

M-<Delback>  移除光标前的一个词

M-d          移除光标后的一个词

C-k          移除从光标到“行尾”间的字符

M-k          移除从光标到“句尾”间的字符

c-@ 开始标记 c-w 标记结束，移除

c-y 召回最近一次被移除的内容

m-y 召回再前一次被移除的内容

c-x u 撤销

c-x c-f 查找一个文件 c-g 关闭

c-x c-s 存储这个文件

【关掉文件备份可以用如下命令：M-x customize-variable <Return> make-backup-files <Return>】

c-x c-b 列出缓冲区

c-x b <文件名> 打开缓冲文件

c-x s 保存多个缓冲区

c-x c-c 全部保存并退出

c-x k 杀死当前缓冲区

m-x replace-string 替换字符串

m-x recover-file 从自动保存文件中恢复

c-u c-v 将本行带到屏幕的最上方

m-x 模式名 切换模式

c-h m 查看主模式文档

c-s 向前搜索

c-r 向后搜索

【你会发现 C-g 会让光标回到搜索开始的位置，而 <Return> 则让光标留在搜索结果上，这是很有用的功能。】

c-x 2 划分两个窗格

c-m-v 滚动另一个窗格

c-x o 移到另一个窗格

ESC ESC ESC 通用的“离开”命令 可用于关闭多余的窗格，或者离开小缓冲

输入 C-h c 之后再输入一个组合键，Emacs 会给出这个命令的简要说明

C-h i 阅读联机手册

#include <cstdio>
#include <cstring>
#include <vector>
std::vector<int> adj[1000];
int f[1000];
int n;

int mex(int v)
{
    bool g[1000]={0};
    int i,w;
    for(i=0;i<adj[v].size();i++)
    {
        w=adj[v][i];
        if(f[w]==-1)
            f[w]=mex(w);
        g[f[w]]=1;
    }
    for(i=0;;i++)
        if(!g[i]) return i;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int m,v,w,sum;
    while(scanf("%d",&n)!=EOF)
    {
        for(v=0;v<n;v++)
        {
            adj[v].clear();
            scanf("%d",&m);
            while(m--)
            {
                scanf("%d",&w);
                adj[v].push_back(w);
            }
        }
        memset(f,-1,sizeof(f));
        while(scanf("%d",&m)!=EOF&&m)
        {
            sum=0;
            while(m--)
            {
                scanf("%d",&v);
                if(f[v]==-1)
                    f[v]=mex(v);
                sum^=f[v];
            }
            if(sum)
                puts("WIN");
            else
                puts("LOSE");
        }
    }
    return 0;
}

差分约束系统介绍 http://imlazy.ycool.com/post.1702305.html

设S[i]为数组Z在[0,i)上包含的数的个数,则对每一组a b c有,S[b+1]-S[a]>=c 即 S[a]-S[b+1]<=-c,建图时对应从S[b+1]到S[a]的一条权为-c的边.同时有隐含条件0<=S[i+1]-S[i]<=1即S[i+1]-S[i]<=1和S[i]-S[i+1]<=0,对应建图.

因为本题求的是可行解组中最小的,所以用最长路径求法.

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
#define maxn 50001
#define inf 0x3f3f3f3f
int n,m,tot;
struct Edge{int w,wt,next;}e[4*maxn];
int start[maxn];
int d[maxn];//单源距离

void add(int v,int w,int wt)
{
    e[tot].w=w;e[tot].wt=wt;
    e[tot].next=start[v];start[v]=tot++;
}

void spfa(int s)
{
    int i,v,N=0;
    deque<int> dq;
    for(v=0;v<n;v++) d[v]=inf;
    d[s]=0;
    dq.push_back(s);dq.push_back(n);
    while(!dq.empty())
    {
        v=dq.front();dq.pop_front();
        if(v==n)
        {if(N++>n) return;dq.push_back(n);}
        else
            for(i=start[v];i!=-1;i=e[i].next)
            {
                if(d[e[i].w]>d[v]+e[i].wt)
                {
                    d[e[i].w]=d[v]+e[i].wt;
                    dq.push_back(e[i].w);
                }
            }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int m,i,a,b,c,maxnum=0;
    scanf("%d",&m);
    tot=0;for(i=0;i<maxn;i++) start[i]=-1;
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(b+1,a,-c);
        if(b+1>maxnum) maxnum=b+1;
    }
    for(i=0;i<maxnum;i++)
    {
        add(i,i+1,1);
        add(i+1,i,0);
    }
    n=maxnum+1;
    spfa(maxnum);
    printf("%d",d[maxnum]-d[0]);
    return 0;
}

转自 http://hi.baidu.com/alpc__ak47/blog/item/033eca25ecceaa3ac9955965.html

一道比较难想的数学题+矩阵乘法题，这个题Jesful同学迅速AC真是犀利啊，首先题目是求floor（（sqrt(2)+sqrt(3)）^(2*n)）就是求floor（（5+2*sqrt（6））^n），考虑（5+2*sqrt（6））^n最后等于a+b*sqrt（6）那么（5-2*sqrt（6））^n就应该等于a-b*sqrt（6），所以有（5+2*sqrt（6））^n+（5-2*sqrt（6））^n=2*a，然后可以观察到（5-2*sqrt（6））^n远小于1 所以floor（（5+2*sqrt（6））^n+（5-2*sqrt（6））^n）=2*a，也就是说floor（（5+2*sqrt（6））^n）=2*a-1，所以只需求得a即可，求a的话就是用递推，即是说构造矩阵用矩阵乘法解决，这样时间复杂度为O（logn）----wr大牛

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
struct mat{int a11,a12,a21,a22;};
mat m[31];
int a,b;

void init()
{
    m[0].a11=5; m[0].a12=2;
    m[0].a21=12;m[0].a22=5;
    for(int i=1;i<=30;i++)
    {
        m[i].a11=(m[i-1].a11*m[i-1].a11+m[i-1].a12*m[i-1].a21)%1024;
        m[i].a12=(m[i-1].a11*m[i-1].a12+m[i-1].a12*m[i-1].a22)%1024;
        m[i].a21=(m[i-1].a21*m[i-1].a11+m[i-1].a22*m[i-1].a21)%1024;
        m[i].a22=(m[i-1].a21*m[i-1].a12+m[i-1].a22*m[i-1].a22)%1024;
    }
}

void modexp(int n)
{
    a=1,b=0;
    int oa,ob;
    for(int i=0;i<=30&&n;i++)
    {
        if(n&1<<i)
        {
            oa=a;ob=b;
            a=(oa*m[i].a11+ob*m[i].a21)%1024;
            b=(oa*m[i].a12+ob*m[i].a22)%1024;
            n-=1<<i;
        }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    init();
    int cas,n;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        modexp(n);
        printf("%d\n",(a+a+1024-1)%1024);
    }
}