「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现) F

【思路】

因为时间是个天然的序,所以我们只需要去考虑蚂蚁的朝向和位置即可.而蚂蚁是否被吃也可以通过是否有和他相向而行的蚂蚁来判断.

用栈来边输入(输入是向右进行的,所以我们就让右行的蚂蚁固定,用左行的蚂蚁来吃与被吃..好残忍= =)边模拟这一过程.(其实只要是链表形式的都可以用来模拟,因为这样会节省时间

【Code】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
struct Star{
    int A,B;
};
stack<Star> Inti;
int N,A,B;
int main(){
    freopen(“in.txt”, “r”, stdin);
    freopen(“out.txt”, “w”, stdout);
    while(~scanf(“%d”,&N)){
        while(!Inti.empty()){
            Inti.pop();
        }
        rep(i,N){
            scanf(“%d%d”,&A,&B);
            //Inti.push_back((Star){A,B,true});
            if(B==1 || (!Inti.empty() && Inti.top().B==0)){
                Inti.push((Star){A,B});
            }else{
                int flag=0;
                while(!Inti.empty()){
                    if(Inti.top().B==1){
                        if(Inti.top().A<A){
                            Inti.pop();
                        }else{
                            flag=1;
                        }
                        if(flag) break;
                    }else break;
                }
                if(!flag){
                    Inti.push((Star){A,B});
                }
            }
        }
        printf(“%d\n”,Inti.size());
    }
    return 0;
}

【输入数据 in.txt】

12
8 1
5 0
3 1
6 0
7 1
4 0
1 1
9 0
2 1
13 0
15 1
32 0
5
4 0
3 1
2 0
1 0
5 0
12
8 0
5 1
3 0
6 1
7 0
4 1
1 0
9 1
2 0
13 1
15 0
32 1

【输出数据】

3
2
4

「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现) A

【题目来源】

「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现) A

【Tip】

找进位规律找的自己恶心吐了,最后跪在了百位进位时忘了加最后的那几次十进位…(最后也是对拍了一个ACcode才找到了错误的地方

思维漏洞还是太大了,或者说这种思维方式不太好.

不过也算是又学会了一点东西.

【My Code】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
int main(){
    freopen(“in_2.txt”, “r”, stdin);
    freopen(“out_2.txt”, “w”, stdout);
    int T,N,M,B,C,EndN,EndM;
    while(~scanf(“%d”,&T)){
        int ca=1;
        while(T–){
            int REG1,REG2,D1,D2,ans=-INF,r1[3],r2[3],r11[3],r22[3];
            D1=D2=0;
            scanf(“%d%d”,&B,&C);
            REG1=B;
            REG2=C;
            red(i,2,0){
                r1[i]=REG1%10;REG1/=10;
                r2[i]=REG2%10;REG2/=10;
            }
            scanf(“%d”,&N);
            rep(i,N+1){//甲得i分,乙得M分
                int D11,D22,all;
                D11=D22=0;all=0;
                M=N-i;
                EndN=B+i;
                EndM=C+M;
                red(i,2,0){
                    r11[i]=EndN%10;EndN/=10;
                    r22[i]=EndM%10;EndM/=10;
                }//百位进位19 十位进位9
                r11[0]=r11[0]-r1[0];
                if(r11[0]) {
                    r11[1]=(r11[0]-1)*9+(9-r1[1])+r11[1];
                    all+=(r11[0]*18+r11[1]*9);
                }else{
                    r11[1]=r11[1]-r1[1];
                    all+=(r11[1]*9);
                }
                r22[0]=r22[0]-r2[0];
                if(r22[0]) {
                    r22[1]=(r22[0]-1)*9+(9-r2[1])+r22[1];
                    all+=(r22[0]*18+r22[1]*9);
                }else{
                    r22[1]=r22[1]-r2[1];
                    all+=(r22[1]*9);
                }
               // printf(“%d\n”,all+N);
                ans=max(ans,all+N);
            }
            printf(“Case %d: %d\n”,ca++,ans);
        }
    }
    return 0;
}

【效率&直观 code】

感觉处理方法类似于数位dp

    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 1005
    int dp[maxn];

    void init(){
        for(int i=1;i<=999;i++){
            if(i%100==0){
                dp[i]=dp[i-1]+19;
            }else if(i%10==0)
                dp[i]=dp[i-1]+10;
            else
                dp[i]=dp[i-1]+1;
        }
        return;
    }

    int main(){
        freopen(“in_2.txt”, “r”, stdin);
        freopen(“out_3.txt”, “w”, stdout);
        int T;
        cin>>T;
        init();
        for(int cas=1;cas<=T;cas++){
            int a,b,k;
            cin>>a>>b>>k;
            int ans=0;
            int tans=0;
            for(int i=0;i<=k;i++){
                tans=dp[a+i]-dp[a]+dp[b+k-i]-dp[b];
               // printf(“%d\n”,tans);
                ans=max(ans,tans);
            }
            cout<<“Case “<<cas<<“: “;
            cout<<ans<<“\n”;
        }
        return 0;
    }

【数据 in_2.txt】

13
000 000
1
000 000
10
000 000
100
001 000
109
001 001
109
123 123
89
458 253
500
327 652
200
320 602
58
227 725
63
102 103
37
023 001
900
21 23
5

【输出】

Case 1: 1
Case 2: 19
Case 3: 199
Case 4: 217
Case 5: 217
Case 6: 179
Case 7: 1013
Case 8: 398
Case 9: 112
Case 10: 126
Case 11: 73
Case 12: 1791
Case 13: 5

Python Learnning Record

【Link】

廖雪峰的python教程

【直接运行py文件】

有同学问,能不能像.exe文件那样直接运行.py文件呢?在Windows上是不行的,但是,在Mac和Linux上是可以的,方法是在.py文件的第一行加上一个特殊的注释:

#!/usr/bin/env python3

print('hello, world')

然后,通过命令给hello.py以执行权限:

$ chmod a+x hello.py

就可以直接运行hello.py了,比如在Mac下运行:

【数据类型和变量】

Python可以处理任意大小的整数,当然包括负整数. (惊了

注意:Python的整数没有大小限制,而某些语言的整数根据其存储长度是有大小限制的,例如Java对32位整数的范围限制在-21474836482147483647

Python的浮点数也没有大小限制,但是超出一定范围就直接表示为inf(无限大)。

整数和浮点数在计算机内部存储的方式是不同的,整数运算永远是精确的(除法难道也是精确的?是的!),而浮点数运算则可能会有四舍五入的误差。

字符串

字符串是以单引号'或双引号"括起来的任意文本,比如'abc'"xyz"等等。请注意,''""本身只是一种表示方式,不是字符串的一部分,因此,字符串'abc'只有abc这3个字符。如果'本身也是一个字符,那就可以用""括起来,比如"I'm OK"包含的字符是I'm,空格,OK这6个字符。

如果字符串内部既包含'又包含"怎么办?可以用转义字符\来标识,比如:

'I\'m \"OK\"!'

表示的字符串内容是:

I'm "OK"!

如果字符串里面有很多字符都需要转义,就需要加很多\,为了简化,Python还允许用r''表示''内部的字符串默认不转义,可以自己试试:

>>> print('\\\t\\')
\       \
>>> print(r'\\\t\\')
\\\t\\

如果字符串内部有很多换行,用\n写在一行里不好阅读,为了简化,Python允许用'''...'''的格式表示多行内容,可以自己试试:

>>> print('''line1
... line2
... line3''')
line1
line2
line3

上面是在交互式命令行内输入,注意在输入多行内容时,提示符由>>>变为...,提示你可以接着上一行输入。如果写成程序,就是:

print('''line1
line2
line3''')

多行字符串'''...'''还可以在前面加上r使用,请自行测试。

空值

空值是Python里一个特殊的值,用None表示。None不能理解为0,因为0是有意义的,而None是一个特殊的空值。

此外,Python还提供了列表、字典等多种数据类型,还允许创建自定义数据类型,我们后面会继续讲到。

在Python中,等号=是赋值语句,可以把任意数据类型赋值给变量,同一个变量可以反复赋值,而且可以是不同类型的变量,例如:

a = 123 # a是整数
print(a)
a = 'ABC' # a变为字符串
print(a)

【整数的除法】
最后解释一下整数的除法为什么也是精确的。在Python中,有两种除法,一种除法是/

>>> 10 / 3
3.3333333333333335

/除法计算结果是浮点数,即使是两个整数恰好整除,结果也是浮点数:

>>> 9 / 3
3.0

还有一种除法是//,称为地板除,两个整数的除法仍然是整数:

>>> 10 // 3
3

你没有看错,整数的地板除//永远是整数,即使除不尽。要做精确的除法,使用/就可以。

因为//除法只取结果的整数部分,所以Python还提供一个余数运算,可以得到两个整数相除的余数:

>>> 10 % 3
1

无论整数做//除法还是取余数,结果永远是整数,所以,整数运算结果永远是精确的。

【字节】

最早的计算机在设计时采用8个比特(bit)作为一个字节(byte),所以,一个字节能表示的最大的整数就是255(二进制11111111=十进制255),如果要表示更大的整数,就必须用更多的字节。比如两个字节可以表示的最大整数是65535,4个字节可以表示的最大整数是4294967295

【编码】

由于计算机是美国人发明的,因此,最早只有127个字符被编码到计算机里,也就是大小写英文字母、数字和一些符号,这个编码表被称为ASCII编码,比如大写字母A的编码是65,小写字母z的编码是122

但是要处理中文显然一个字节是不够的,至少需要两个字节,而且还不能和ASCII编码冲突,所以,中国制定了GB2312编码,用来把中文编进去。

UTF-8:可变长编码.

Unicode:不可变长全码.

转换过程:

 

浏览网页的时候,服务器会把动态生成的Unicode内容转换为UTF-8再传输到浏览器:

所以你看到很多网页的源码上会有类似<meta charset="UTF-8" />的信息,表示该网页正是用的UTF-8编码。
【python的字符串】
搞清楚了令人头疼的字符编码问题后,我们再来研究Python的字符串。

在最新的Python 3版本中,字符串是以Unicode编码的,也就是说,Python的字符串支持多语言,例如:

>>> print('包含中文的str')
包含中文的str

对于单个字符的编码,Python提供了ord()函数获取字符的整数表示,chr()函数把编码转换为对应的字符:

>>> ord('A')
65
>>> ord('中')
20013
>>> chr(66)
'B'
>>> chr(25991)
'文'

如果知道字符的整数编码,还可以用十六进制这么写str

>>> '\u4e2d\u6587'
'中文'

【网络中文本的比特流传输转换】
Python对bytes类型的数据用带b前缀的单引号或双引号表示:

x = b'ABC'

要注意区分'ABC'b'ABC',前者是str,后者虽然内容显示得和前者一样,但bytes的每个字符都只占用一个字节。

以Unicode表示的str通过encode()方法可以编码为指定的bytes,例如:

>>> 'ABC'.encode('ascii')
b'ABC'
>>> '中文'.encode('utf-8')
b'\xe4\xb8\xad\xe6\x96\x87'
>>> '中文'.encode('ascii')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
UnicodeEncodeError: 'ascii' codec can't encode characters in position 0-1: ordinal not in range(128)

纯英文的str可以用ASCII编码为bytes,内容是一样的,含有中文的str可以用UTF-8编码为bytes。含有中文的str无法用ASCII编码,因为中文编码的范围超过了ASCII编码的范围,Python会报错。

bytes中,无法显示为ASCII字符的字节,用\x##显示。

反过来,如果我们从网络或磁盘上读取了字节流,那么读到的数据就是bytes。要把bytes变为str,就需要用decode()方法:

>>> b'ABC'.decode('ascii')
'ABC'
>>> b'\xe4\xb8\xad\xe6\x96\x87'.decode('utf-8')
'中文'

要计算str包含多少个字符,可以用len()函数:

>>> len('ABC')
3
>>> len('中文')
2

len()函数计算的是str的字符数,如果换成byteslen()函数就计算字节数:

>>> len(b'ABC')
3
>>> len(b'\xe4\xb8\xad\xe6\x96\x87')
6
>>> len('中文'.encode('utf-8'))
6

可见,1个中文字符经过UTF-8编码后通常会占用3个字节,而1个英文字符只占用1个字节。

 

【格式化输入输出】

最后一个常见的问题是如何输出格式化的字符串。我们经常会输出类似'亲爱的xxx你好!你xx月的话费是xx,余额是xx'之类的字符串,而xxx的内容都是根据变量变化的,所以,需要一种简便的格式化字符串的方式。

在Python中,采用的格式化方式和C语言是一致的,用%实现,举例如下:

>>> 'Hello, %s' % 'world'
'Hello, world'
>>> 'Hi, %s, you have $%d.' % ('Michael', 1000000)
'Hi, Michael, you have $1000000.'

你可能猜到了,%运算符就是用来格式化字符串的。在字符串内部,%s表示用字符串替换,%d表示用整数替换,有几个%?占位符,后面就跟几个变量或者值,顺序要对应好。如果只有一个%?,括号可以省略。

常见的占位符有:

%d 整数
%f 浮点数
%s 字符串
%x 十六进制整数

其中,格式化整数和浮点数还可以指定是否补0和整数与小数的位数:

>>> '%2d-%02d' % (3, 1)
' 3-01'
>>> '%.2f' % 3.1415926
'3.14'

如果你不太确定应该用什么,%s永远起作用,它会把任何数据类型转换为字符串:

>>> 'Age: %s. Gender: %s' % (25, True)
'Age: 25. Gender: True'

有些时候,字符串里面的%是一个普通字符怎么办?这个时候就需要转义,用%%来表示一个%

>>> 'growth rate: %d %%' % 7
'growth rate: 7 %'

【list】

如果要取最后一个元素,除了计算索引位置外,还可以用-1做索引,直接获取最后一个元素:

> classmates[-1]
'Tracy'

往后分块记笔记...

【python3学习 模块】

python3内置模块文档: https://docs.python.org/3/library/functions.html

python3自己写模块及使用: 廖雪峰-使用模块

python3安装第三方模块: 安装第三方模块