先上一张最终的结果:

Screenshot 2019-04-08 at 08.03.06.png

这次资格赛总的来说表现的还不错,可惜第一题没仔细读题处理大数据出了问题。

Foregone Solution

  • 题目链接
    Foregone Solution
  • 题意
    将一个数字分成两个数字相加,使得这两个数字任何一位均不为4。其中有1分该数据不超过1e100,其他数据不超过1e9。
  • 分析
    将数字逐位处理,如果遇到4拆分成两个部分,如果不是4直接给某一个答案加上这一位即可。
  • 代码
    (本段代码未特别处理大数据)
#include <bits/stdc++.h>
using namespace std;
void slove(int n){
    int temp = 1;
    int ans1=0,ans2=;
    while (n){
        if (n%10==4){
            ans1+=2*temp;
            ans2+=2*temp;
        }
        else ans1+=n%10*temp;
        n/=10;
        temp*=10;
    }
    cout<<ans1<<' '<<ans2;
    return ;    
}
int main(){
    int t;
    cin>>t;
    for (int i=1;i<=t;i++){
        int n;
        cin>>n;
        cout<<"Case #"<<i<<": ";
        slove(n);
        cout<<endl;
    }
}

You Can Go Your Own Way

  • 题目链接
    You Can Go Your Own Way
  • 题意
    在N*N的网格中,每次只能向右或者向下走,当前已经规划出一条路径,请你设计出一个没有任意一段完全相同的路径(没有任意一段完全相同指对于已知路径中任意的A->B,设计的路径也不能有A->B,但是A与B本身均是可以到达的)
  • 分析
    乍一看要设计出很复杂的递归回溯算法什么的,但是分析后发现,只要将读入数据的E与S对调即可。在对角线之外的情况路线完全分离故可行,在对角线之中的情况仅有:交错与途径同一点组成十字两种情况,故该种做法可行。
  • 代码
#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    for (int i=1;i<=t;i++){
        int nn;
        cin>>nn;
        string s;
        cin>>s;
        printf("Case #%d: ",i);
        for (auto i:s){
            if (i=='S')printf("E");
            else printf("S");
        }
        printf("\n");
    }
}

Cryptopangrams

  • 题目链接
    Cryptopangrams
  • 题意
    本题描述了一种加密方法。首先将26个字母映射到26个不同的素数(规模不超过1e100)上,其中A对于的素数最小,Z对应的素数最大,以此类推。然后将要加密的文本两两相邻的字母所对应的素数相乘,对于长度为k的字符串,可以生成长度为k-1的数字序列。现给你这个数字序列,求还原后的字符串,保证还原后的字符串26个字母至少各出现一次。
  • 分析
    最开始被两个素数相乘这个条件给蒙骗了,以为需要将大数分解成两个素数,经思考后发现对于序列中相邻的两个数实际上为(x*y)和(y*z)因此只需任意一对数的最大公约数后即可求出该处对应的素数,之后即可递推出所有位置进而处理出对应关系。但是还有一点需要注意:不能直接选取最开始的两个数字,它应付不了此类情况:ABA...这样求出的最大公约数并不是B而是AB。因此需要找到序列中任何一对不相同的数字来求最大公约数。
  • 代码
import java.math.BigInteger;
import java.util.Scanner;


public class Solution {
    private static BigInteger _0=BigInteger.valueOf(0);

    private static BigInteger gcd(BigInteger a, BigInteger b){
        if (b.compareTo(_0)==0){
            return a;
        }
        else {
            return gcd(b,a.mod(b));
        }
    }

    public static void main(String args[]) {

        Scanner scanner = new Scanner(System.in);
        int t;
        t=scanner.nextInt();
        for (int ii = 1; ii <= t; ii++) {
            scanner.nextBigInteger();
            int l=scanner.nextInt();

            System.out.printf("Case #%d: ",ii);

            BigInteger []input=new BigInteger[200];
            BigInteger []ans=new BigInteger[200];
            for (int i=0;i<l;i++){
                input[i]=scanner.nextBigInteger();
            }

            int pos = 0;
            for (int i=0;i<l;i++){
                if (input[i].compareTo(input[i+1])!=0){
                    ans[i+1]=gcd(input[i],input[i+1]);
                    pos=i+1;
                    break;
                }
            }
            for (int i=pos-1;i>=0;i--){
                ans[i]=input[i].divide(ans[i+1]);
            }
            for (int i=pos+1;i<=l;i++){
                ans[i]=input[i-1].divide(ans[i-1]);
            }

            BigInteger []hashtable=new BigInteger[30];

            for (int i=0;i<=l;i++){
                for (int j=0;j<26;j++){
                    if (hashtable[j]==null){
                        hashtable[j]=ans[i];
                        break;
                    }
                    else {
                        final int i1 = hashtable[j].compareTo(ans[i]);
                        if (i1 ==0){
                            break;
                        }
                        else if (i1 >0){
                            for (int k=25;k>j;k--){
                                hashtable[k]=hashtable[k-1];
                            }
                            hashtable[j]=ans[i];
                            break;
                        }
                    }
                }
                if (hashtable[25]!=null)break;
            }

            for (int i=0;i<=l;i++){
                for (int j=0;j<26;j++){
                    if (hashtable[j].compareTo(ans[i])==0){
                        System.out.print((char)(j+(int)'A'));
                        break;
                    }
                }
            }
            System.out.print("\n");
        }
        scanner.close();
    }
}

Dat Bae

  • 题目链接
    Dat Bae
  • 题目大意
    本题为交互题。每组数据指定N,B,F三个数字,允许发送长度为N的01串,将返回去除B位,总长度为N-B的01串,求出丢失的是哪些位。其中N不超过1024,B不超过15,F最小为5。
  • 分析
    表面上看起来5次机会最多处理25种情况,而本题情况显然最大有1024取15种,远远大于25,但实际上这也是本题的障眼法。首先第一次依次输出16个1,16个0相间排列的询问,可以将处理1024长度的字符串分割成处理长度16的字符串。即使15个缺失位全部在同一区间内,长度16的1或0也可以将其分割开。之后输出8个1,8个0相间排列的询问,将原本长度本应为16的区间分成两部分处理,判断前8位缺失多少位,后8位缺失多少位,以此类推。最终通过16,8,4,2,1个连续01相间排列的串刚好共5次即可得到最终缺失的位数。
#include <bits/stdc++.h>
using namespace std;

void generate(int n,int l,char *a){
    int t=0,pos=0;
    while (pos!=n){
        if (pos/l%2) a[pos++]='0';
        else a[pos++]='1';
    }
    a[pos]=0;
}
string s[5];

void slove(string str,int ll,int l,int len,int now){
    if (str.length()==0){
        for (int i=0;i<len;i++){
            cout<<ll+i<<' ';
        }
    }
    else if (len==str.length()){
        return ;
    }
    else if (now==0){
        if (str[0]=='0')cout<<ll<<' ';
        else cout<<ll+1<<' ';
    }
    else if (str[str.length()-1]=='1'){
        int minn=min(1<<now,len);
        slove(s[now-1].substr(l,str.length()),ll,l,minn,now-1);
        slove("",ll+(1<<now),l+str.length(),len-minn,now-1);
    }
    else {
        for (int i=0;i<str.length();i++){
            if (str[i]=='0'){
                slove(s[now-1].substr(l,i),ll,l,1<<now,now-1);
                slove(s[now-1].substr(l+i,str.length()-i),ll+(1<<now),l+i,len-(1<<now),now-1);
                break;
            }
        }
    }
}

int main(){
    int t;
    cin>>t;
    while (t--){
        int n,b,f;
        cin>>n>>b>>f;
        char a[1100];
        for (int k=4;k>=0;--k){
            generate(n,1<<k,a);
            cout<<a<<endl;
            fflush;
            cin>>s[k];
        }
        int pre=0;
        int t=0;
        int tot=0;
        for (int i=1;i<s[4].size();i++){
            if (s[4][i]!=s[4][i-1]){
                slove(s[3].substr(pre,i-pre),tot,pre,16,3);
                pre=i;
                tot+=16;
            }
        }
        slove (s[3].substr(pre),tot,pre,n-b-pre+(b-(tot-pre)),3);
        cout<<endl;
        fflush;
        cin>>n;
        if (n==-1)break;

    }
}
/*
以下为参考测试数据
3
10 2 10
11111111
11111110
11100001
10011001
01010101
1
5 2 10
111
111
110
101
011
1
32 8 10
111111111111000000000000
111100000000111111110000
000011110000111100001111
110011001100110011001100
101010101010101010101010
1

ans:
0 3
0 9
0 1 2 3 28 29 30 31
*/

分段打表

对于某些依赖项仅与n有关或仅与前几项有关时的打表方法。

  • 一个典型的例子是求1e9内n阶乘取模的运算。
    可以提前处理出1e7,2e7...的值,如果需要某个值时先取出低于它的最大的已知数从当前位置开始计算。间隔可以不是1e7,根据需要(权衡时间与程序大小限制)也可以更改为其他的
  • 另一个例子是求斐波那契数列取模的运算。
    比如求1e9内的斐波那契取模运算,可以求1e7,1e7+1,2e7,2e7+1...由此来在O(1e7)的时间内求出1e9内任意斐波那契数。

打表找规律

某些题目中的输出与输入有着较为简单的数学关系,时间复杂度估算O(1)(多项式)或者O(logn)(快速幂)或者O(n)(递推式)的均可考虑打表找规律。
对于这一类题目输入数据一般每个测试点只有一或少数几个数,存在ans=f(x)或ans=kf(x)等其他关系,并且由题目的意思答案通常要在输入数据经过一系列复杂的计算得到。
对于该类题目通常有以下几种找规律方法:

  • 通过暴力列出前若干项答案
  • 判断数据的增长级别(确认大致是多项式级还是指数级等)
  • 尝试猜测公式,并列出更多数据加以验证。
  • 难以猜测的尝试前后项作差或者考虑前缀和等
  • 除上一点还可尝试分类(如奇偶单独处理,质数合数单独处理,2^k单独处理等等)

注意:本文基于lnmp一键安装包安装Nginx环境

进入Nginx配置文件夹

cd /usr/local/nginx/conf/vhost/

如果不是通过lnmp一键安装包安装的Nginx环境请自行搜索配置文件夹位置。

备份配置文件

cp ./你的网站.conf ./你的网站.conf.bak

修改配置文件

nano ./你的网站.conf

server
    {
        listen 80;
        …………
    }

中的内容全部删去,并添入以下信息:

server
    {
        listen 80;
        #listen [::]:80;
        server_name 你的网站 ;
        rewrite ^(.*)$  https://$host$1 permanent;
    }

Ctrl+x,回车,选择y,保存退出
如果在第一步中提示nano不存在,可使用

sudo apt-get install nano 

sudo yum install nano 

安装nano程序。

重启lnmp一键安装包环境

lnmp restart

如果不是通过lnmp一键安装包安装的Nginx环境可以通过重启服务器方式来刷新nginx的配置规则。

这是nginx的设置时没有注意支持pathinfo导致的,具体关于php pathinfo的信息可以在网上搜索到。
以下是该问题的解决方案

使用lnmp一键安装包安装的 Nginx

进入Nginx配置文件夹

cd /usr/local/nginx/conf/

备份 enable-php.conf 文件

cp ./enable-php.conf ./enable-php.conf.bak

修改 enable-php.conf 文件

nano ./enable-php.conf

在结尾大括号前添加如下内容:

include pathinfo.conf;

修改后文件内容为:

    location ~ [^/]\.php(/|$)
    {
        #try_files $uri =404;
        fastcgi_pass  unix:/tmp/php-cgi.sock;
        fastcgi_index index.php;
        include fastcgi.conf;
        include pathinfo.conf;
    }

如果提示nano命令不存在,可使用

sudo apt-get install nano

sudo yum install nano

安装nano程序

重启lnmp环境

lnmp restart

自行安装的Nginx

参考资料:服务器环境配置 - Typecho Docs

一般的出现这种情况时,nginx.conf里的的location设置都是类似这样

location ~ .*\.php$

要支持pathinfo,要改成

location ~ .*\.php(\/.*)*$

然后在location里加上

            set $path_info "";
            set $real_script_name $fastcgi_script_name;
            if ($fastcgi_script_name ~ "^(.+?\.php)(/.+)$") {
                    set $real_script_name $1;
                    set $path_info $2;
            }
            fastcgi_param SCRIPT_FILENAME $document_root$real_script_name;
            fastcgi_param SCRIPT_NAME $real_script_name;
            fastcgi_param PATH_INFO $path_info;

在某些老版本的php里面,可能还要打开php.ini里的cgi.fix_pathinfo

cgi.fix_pathinfo = 1

设置完之后重启服务器

关于本教程

Typecho是什么?

Typecho 是由 type 和 echo 两个词合成的,来自于开发团队的头脑风暴。

Type,有打字的意思,博客这个东西,正是一个让我们通过打字,在网络上表达自己的平台。Echo,意思是回声、反馈、共鸣,也是PHP里最常见、最重要的函数,相信大部分PHP爱好者都是从 echo 'Hello,world!'; 开始自己的PHP编程之路的。

名称就表明 Typecho 是一款博客程序,它在 GPL version 2 许可证下发行,基于 PHP (需要 PHP5 以上版本)构建,可以运行在各种平台上,支持多种数据库(Mysql, PostgreSQL, SQLite)。

为什么要使用Typecho?

轻量高效

仅仅 7 张数据表,加上不足 400KB 的代码,就实现了完整的插件与模板机制。超低的 CPU 和内存使用率,足以发挥主机的最高性能。

先进稳定

原生支持 Markdown 排版语法,易读更易写。支持 BAE/GAE/SAE 等各类云主机,即使面对突如其来的高访问量,也能轻松应对。

简洁友好

精心打磨过的操作界面,依然是你熟悉的面孔,更多了一份成熟与贴心。每一个像素的剪裁,都只为离完美更进一步。

有关链接

Typecho官网
Github上的typecho


- 阅读剩余部分 -