google code jam2016资格赛题解

A. Counting Sheep
小数据暴力呗。大数据也一样。。
B. Revenge of the Pancakes
小数据暴力呗。大数据没做。。
C. Coin Jam
小数据暴力呗。大数据没做。。
D. Fractiles
题意:一个序列由两种字符组成:L、G.给出k,c,s。表示序列初始长度k,变换了c次。每次变换:L的地方用最初始序列代替,G的地方用k个G代替。
现序列各个位置的值是看不到的,你可以选择查看其中的s个位置的值。问:能否通过小于等于s次查看,来推断出现序列是否包含G。
这题我是这样做的。小数据大数据一个做法。
如果查看一个位置发现是G,那么我们就知道序列是含有G的了,所以问题其实是在问:有没有一种查看的策略使得在查看的值都是L的情况下,可以断定序列必定没有G。
我们可以把整个变换的过程画出来,可以发现是一棵k叉树(注意一点这里我把原始序列的k个结点最为统一的“根结点”)。叶子节点是现序列。关键一点在于当得到了位置pos的值是L之后,我们就知道了pos位置的值是L之后,就知道了pos的父节点是L,它的父节点也是L。换言之,pos到树根的路径上的结点都是L。
那么为了尽可能通过一次查看得到最多信息,我们可以查看根节点的第二个子结点的第三个子结点的…………(一直到叶子结点)的值。这样就得到了min(c,k)个连续位置的值,接下来重复这个查看过程就行。
这个还是有个图比较好解释。。下次加个图。

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll a[110];
ll ans[110],cnt;
inline ll min(ll a,ll b){return a<b?a:b;}
int main()
{
    //freopen("D-large.in","r",stdin);
    //freopen("D-large.out","w",stdout);
    ll i,j;
    int k,c,s;
    int t,cases=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&k,&c,&s);
        printf("Case #%d:",++cases);
        if(c==1)
        {
            if(s<k) {printf(" IMPOSSIBLE\n");continue;}
            for(i=1;i<=k;i++) printf(" %d",i);
            printf("\n");
            continue;
        }
        if(k==1)
        {
            if(s<k) {printf(" IMPOSSIBLE\n");continue;}
            printf(" 1\n");continue;
        }
        cnt=0;
        a[0]=1;a[1]=k;
        for(i=2;i<=c;i++)
            a[i]=a[i-1]*(ll)k;
        for(i=1;i<=k;)
        {
            ll tmp=0;
            for(j=-1;j<=c-2;j++)
            {
                if(i+j+1<=k)
                    tmp+=(i+j)*a1;
                else
                    tmp+=(k-1)*a1;
            }
            ans[++cnt]=tmp+1;
            i+=min(c,k-i+1);
        }
        if(s<cnt) {printf(" IMPOSSIBLE\n");continue;}
        for(i=1;i<=cnt;i++) printf(" %I64d",ans[i]);
        printf("\n");
    }

    return 0;
}

linux内核模块编程笔记

最近因为实验室项目,开始接触了一点linux内核模块编程
内核编译选项.config所在路径:/usr/src/相应内核版本/.config
内核符号表:在编写内核模块的时候,因为LKM是动态加载到内核中,也就是说这时的内核是在内存中运行的,所以正确获取内核函数和变量的地址很重要。如果我们在内核模块中直接将地址写死,那么显然不通用,在另一个内核上可能地址就变了。内核符号表就是用于解决这个问题。每个内核都有其内核符号表,里面是内核导出的符号及其地址。我们编写的内核模块通过访问这个内核符号表就可以得到当前正在运行的内核的可用函数和变量的确切地址。
那么怎样使用内核未导出的符号呢?
我们可以使用kallsyms_lookup_name(char*)这个函数,该函数参数是符号名,返回unsigned long型的函数/变量地址。这个方法有个前提,那就是kallsyms_lookup_name(char*)这个符号本身是被内核导出的,所以要用CONFIG_KALLSYMS=y来编译内核,或者修改内核源码中的kallsyms.c文件,增加EXPORT_SYMBOL(kallsyms_lookup_name);手动将该符号导出
————————————————————————————————————————————————————————————————————————————
过程中的问题和要点:
linux内核的三种内存模型
page结构中的_count和_mapcount
_mapcount:在页表中每增加一个映射项,_mapcount就加1.初始值是-1

使用page_address之后发现所有页帧的虚拟地址都是在内核地址空间?what the fuck
__________________________
x86_64的内存地址空间需要研究
——————————————————————————————
读某个内核虚拟地址出错。BUG: unable to handle kernel paging request at ffff880020000000

找到读取物理内存内容的方法了,如下:
前面失败的原因是较新版本的linux内核限制了对/dev/mem的读取,默认只能读取前1M字节的数据。解决方法时修改.config中的CONFIG_X86_PAT=n,CONFIG_STRICT_DEVMEM=n.然后重新编译内核
编译内核过程(抱歉,不要嫌弃我菜,我经常忘。所以记一下)
make menuconfig生成.config(如果要编译的内核和现有内核版本相同,可以从/boot/config-版本号 copy一份放到源码根目录)
make modules 编译一下内核模块
make modules_install 安装内核模块(到/lib/modules目录)
make install 安装内核(copy 生成的内核映像到/boot下面,修改gurb启动项等)

由于/dev/mem是整个物理地址空间的映像,包括了IO端口、ROM的地址,并不全是RAM,所以要先读取/proc/iomem文件得到System RAM的地址分布,之后读取System RAM的部分即可
代码如下,注意不要读到RAM之外的地方,可能会导致出错。

#include<stdio.h>
#include<string.h>
#include<unistd.h>
#include<sys/mman.h>
#include<sys/types.h>
#include<sys/stat.h>
#include<fcntl.h>
typedef long long ll;
const ll max_read=10000000;
char buf[max_read+10];
typedef struct Node{
	ll be,en;
}Node;
Node node[10010];
int cnt;
int main()
{
	freopen("/proc/iomem","r",stdin);
	cnt=0;
	int i;
	while(gets(buf))
	{
		int len=strlen(buf);
        if(strstr(buf,"System RAM")==NULL) continue;
        char *s=buf;
        strtok(s,":");
        printf("%s\n",s);
        char tmp;
        cnt++;
        sscanf(s,"%llx-%llx",&node[cnt].be,&node[cnt].en);
    }
	
    int fdmem,fdout;
    fdmem=open("/dev/mem", O_RDWR|O_SYNC);
	fdout=open("memdump.txt",O_CREAT|O_RDWR|O_SYNC);
    if ((fdmem == -1) || (fdout==-1))
    {
		printf("open err\n");
        return -1;
    }
	for(i=1;i<=cnt;i++)
    {
        ll be=node[i].be,en=node[i].en;
        lseek(fdmem,be,SEEK_SET);
        printf("read %llx-%llx\n",be,en);
        while(1)
        {
            if(en-be+1<=max_read)
            {
                read(fdmem,buf,en-be+1);
                printf("read %llx-%llx\n",be,en);
                write(fdout,buf,en-be+1);
                break;

            }
            read(fdmem,buf,max_read);
            printf("read %llx-%llx\n",be,be+max_read-1);
            write(fdout,buf,max_read);
            be+=max_read;
        }
    }
	close(fdmem);
	close(fdout);
	
    return 0;
}