博文
[zjut-oj]密码截获(2006-08-20 01:22:00)
摘要：密码截获
Time Limit:1000MS Memory Limit:1024K
Description:Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化ABBA->12ABBA,ABA->ABAKK,123321->51233214 。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？
Input:测试数据有若干行字符串，包括字母，数字，符号。（字母区分大小写）
Output:与输入相对应每一行输出一个整数，代表最长有效密码串的长度。
Sample Input:ABBA
12ABBA
A
ABAKK
51233214
abaaab
Sample Output:4
4
1
3
6
5
Source:Jin Qiwei
后来才发现只要80长就够了，所以测试数据很弱，不用DP也行。
/*
#include<stdio.h>
#include<string.h>
#include<memory.h>
#include<assert.h>
#define MAX_LEN 80
char szInput[MAX_LEN+1];
unsigned char B[MAX_LEN+1][MAX_LEN];
int length;
int getcode()
{
int i,j,notfound1,notfound2=0;
if(length<2)
return 1;
memset(B,0,(length+1)*MAX_LEN);
for(i=0;i<2;++i)
{
for(j=0......
[TOJ]1010数素数(2006-04-25 13:04:00)
摘要：数素数（http://acm.tongji.edu.cn/showproblem.php?problem_id=1010）
Problem
素数是的只能被1和它本身整除的自然数。判断一个数是素数的方法是使用2到该数的平方根的素数除它，若有能整除的则该数不是素数。
其实是个简单问题，但对于给出的数据范围（0<M<N<1000000），总是迫使我寻找更快更省的方法。
一开始我就想找到一种数学方法，如果找到了当然是最快最省的，但是，还没找到，于是只好用笨的方法。
1、用素数的定义
素数是的只能被1和它本身整除的自然数。那就从2到sqrt(n)进行试除，如果有一个数能整除n，那n就不是素数，否则n就是素数。
如果不仔细想，会认为这样做已经是非常快了，其实做了很多多余的工作，以下简单分析：首先从奇偶性上看，所有的素数中只有2是偶数，也就是说几乎所有素数都是奇数，而在试除的过程中，我们还用4,6,8之类的偶数去试除，真是愚蠢到家了。同样的道理，如果3不能整除的，那所有的3的倍数也不能整除，那也不必用6,9,12去试除了。
稍微进行改进的方法是，建立素数表，于是判断一个数n是否是素数就可以用2到sqrt(n)间的素数去除n，如果有一个素数能整除n，那n就不是素数，否则n就是素数。
我说‘稍微’改进，实际上对于基于‘试除’的求素数方法，已经是达到了极致，同时对于n比较大的数，进行试除次数也会大大降低。以下数据可以说明问题：
n= sqrt(n)= 直接试除次数 基于素数表试除次数
10000 100 98 25
&nbs......
[TOJ]1072输出你自己的代码(2005-08-15 17:35:00)
摘要：输出你自己的代码
Time Limit:1s Memory Limit:1000k Special Judge
Total Submit:3800 Accepted:1174
--------------------------------------------------------------------------------
Problem
你曾经看到过这样的程序吗？当它运行的时候，将会输出一些字符，这些字符恰好组成了这个程序的代码本身。
请你写这样的一个程序。
请注意，你的程序运行时将不能访问到源程序（系统已经将源代码删除）。
Input
本题没有输入数据。
Output
输出必须和你提交的代码本身一致。
那个回车弄得我好晕，不过后来还是成功了！
#include<stdio.h>
int main(){char *s;printf("#include<stdio.h>\n");printf(s,34,92,34,34,s="int main(){char *s;printf(%c#include<stdio.h>%cn%c);printf(s,34,92,34,34,s=%c%s%c,34);return 0;}",34);return 0;}......
[TOJ]1047自然数序列(2005-08-08 20:02:00)
摘要：自然数序列
Time Limit:1s Memory Limit:32768k
Total Submit:1938 Accepted:1280
下载样例程序(PE)
下载样例程序(ELF)
--------------------------------------------------------------------------------
Problem
题目的描述
有一个由集合{1，2，……，n}（即自然数集的前N项）全体构成的长度为N的无重复项数列，请在每个数字之前加上“+”或“-”构成一个代数式，每个代数式产生一个代数和，输出所有代数和中的最小非负和
In
第1行：一个正整数t，测试数据个数
第2至t+1行：N(N<=1,000,000)
Out
最小非负和，每行一个
Sample Input
2
1
2
Sample Output
1
1
考虑到任意连续的四个自然数可以调整+-号使和为0，这道题就成纸老虎了。
对于任意的n;
1,2,3,...,n
分成这样的一些段
1 ... (n-7,n-6,n-5,n-4),(n-3,n-2,n-1,n)
...
#include<iostream.h>
int main()
{
int w[4]={0,1,1,0};
int n;
long m;
cin>>n;
while(n--)
{
cin>>m;
cout<<w[m%4]<<endl;
}
return 0;
}......
[TOJ]1026整除65的多项式(2005-07-28 18:09:00)
摘要：整除65的多项式
Time Limit:1s Memory Limit:1000k
Total Submit:1749 Accepted:1157
下载样例程序(PE)
--------------------------------------------------------------------------------
Problem
f(x)=5*x^13+13x^5+kax. 输入非负整数k, (k<10000) 找到最小的正整数a,使得对于任意整数x, 65|f(x) 若不存在这样的a,输出 "no" (无引号)
Input
有多组输入，每行一个k.
Output
每行输出一个a
Sample Input
9
Sample Output
63
Source
fairfox
我喜欢这道题，因为它的数学性质重一些，我在纸上算了半天，结果编了一小段程序搞定，虽然很简单我还是把我的推导过程写一下。
用到的数学知识就是初等数论吧，虽然我还没学，就我所了解的（初中的时候数学竞赛有介绍同余理论）做了一些推理得出的。
首先观察出65=5*13，５和13都是素因数，假设f(x)被65整除，那么f(x)一定能被5整除，因为f(x)=5*x^13+13x^5+kax，所以马上得到，一定满足13x^5+kax被5整除，同样的道理可以得到5x^13+kax一定要被13整除。我引这样一种记法，如果一个数n被数m除余r的话，即n%m==r，那么记为n≡r(mod m)。
这样的式子称为同余式，同余式跟等式在运算上非常的相似，有如下一些运算定律：
如果
n1≡r1(mod m)
n2≡r2(mod m)
那么
n1+n2≡r1+r2(mod m)
n1*n2≡r1*r2(mod m)
n1^k≡r1^k(mod m) [k=0,1,2...]
这就是一......
[TOJ]1138多项式乘法(2005-07-20 15:42:00)
摘要：多项式乘法
Time Limit:1s Memory Limit:500k
Total Submit:215 Accepted:94
--------------------------------------------------------------------------------
Problem
请编程序把含有乘法运算的代数多项式表达式改写成不含乘法的代数多项式。为简化计算，特做以下约定： (1) 代数多项式表达式中只涉及一个代数符号a； (2) 含有乘法运算的代数多项式表达式都是两个不含乘法运算的代数多项式直接相乘的形式，而且这两个参加乘法的代数多项式都用圆括号括起来了。乘法用符号表示，不得省略。 (3) 常数项以外的各项都是ya^x的形式，其中x为该项的系数，而y是该项的指数。1=x 时，不得简写成ya^，应写成ya^1。而1=y时，不得简写成a^x，应写成1a^x。
Input
输入：每行一个含有乘法的代数多项式表达式。本题有多组数据。
Output
输出：每行输出一个问题的解。要求指数大的项不能出现在指数小的项之后，指数相同的项必须合并同类项。不允许出现不必要的空白字符。
Sample Input
(5a^2+3a^1+2)*(4a^1+1)
(5a^1+1)* (5a^1+1)
Sample Output
20a^3+17a^2+11a^1+2
25a^2+10a^1+1
#include<iostream.h>
struct polynode
{
polynode *next;
int a,e;//ax^e
};
class poly
{
protected:
polynode *head,*tail;
void additem(char......
[TOJ]1021麻将游戏(2006-04-22 13:18:00)
摘要：麻将游戏
Time Limit:1s Memory Limit:1024k
Total Submit:3119 Accepted:531
下载样例程序(PE)
下载样例程序(ELF)
--------------------------------------------------------------------------------
Problem
在一种"麻将"游戏中，游戏是在一个有W＊H格子的矩形平板上进行的。
每个格子可以放置一个麻将牌，也可以不放（如图所示）。玩家的目标是将平板上的所有可通过一条路径相连的
两张相同的麻将牌，从平板上移去。最后如果能将所有牌移出平板，则算过关。
这个游戏中的一个关键问题是：两张牌之间是否可以被一条路径所连接，该路径满足以下两个特性：
1. 它由若干条线段组成，每条线段要么是水平方向，要么是垂直方向。
2. 这条路径不能横穿任何一个麻将牌 (但允许路径暂时离开平板)。
这是一个例子：
在（1，3）的牌和在(4, 4)的牌可以被连接。(2, 3)和(3, 4)不能被连接。
你的任务是编一个程序，检测两张牌是否能被一条符合以上规定的路径所连接。
Input
第一行为一整数N表示有N组测试数据。
每组测试数据的第一行有两个整数w，h （1<=w，h<=75），表示平板的宽和高。
接下来h行描述平板信息，每行包含w个字符，如果某格子有一张牌，则这个格子上有个'X'，否则是一个空格。
平板上最左上角格子的坐标为（1，1），最右下角格子的坐标为（w,h）。
接下来的若干行，每行有四个数x1， y1， x2， y2 ，且满足1<=x1,x2<=w，1<=y1,y2<=h，
表示两张牌的坐标（这两张牌的坐标总是不同的）。
如果出现连续四个0，则表示输入结束。
Output
输出文件中，对于每一对牌输出占一行，为连接这一对......
[TOJ]1029埃及分数(2005-06-10 13:41:00)
摘要：埃及分数
Time Limit:2s Memory Limit:1000k
Total Submit:2302 Accepted:340
下载样例程序(PE)
下载样例程序(ELF)
--------------------------------------------------------------------------------
Problem
在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。
如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。
对于一个分数a/b,表示方法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
如：
19/45=1/3 + 1/12 + 1/180
19/45=1/3 + 1/15 + 1/45
19/45=1/3 + 1/18 + 1/30,
19/45=1/4 + 1/6 + 1/180
19/45=1/5 + 1/6 + 1/18.
最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。
给出a,b(0〈a〈b〈1000),编程计算最好的表达方式。
Input
第一行:N 表示有N组测试数据，每组测试数据为一行包含a,b(0〈a〈b〈1000)。
Output
每组测试数据若干个数，自小到大排列，依次是单位分数的分母。
Sample Input
1
19 45
Sample Output
5 6 18
Source
oibh
#include <iostream>
#include <algorithm>
#include <cstdlib>
......
[TOJ]1203程序分析器(2005-06-07 18:50:00)
摘要：程序分析器
Time Limit:2s Memory Limit:2000k
Total Submit:26 Accepted:4
--------------------------------------------------------------------------------
Problem
Tiny Basm语言(简称为TB语言)的巴科斯-瑙尔范式(BNF)为：
<程序> ::= <语句> ¿ { <语句> ¿ }
<语句> ::= <行号> ÿ <语句体>
<语句体> ::= <累加语句> | <输出语句> | <转移语句> | <条件语句> | <结束语句>
<累加语句> ::= <变量> + <整数>
<输出语句> ::= <变量> ?
<转移语句> ::= GO ÿ <行号>
<条件语句> ::= IF ÿ <变量> = <整数> ÿ <转移语句>
<结束语句> ::= END
<变量> ::= <字母>......
[TOJ]1011阶乘末尾非零数求和(2005-06-05 15:27:00)
摘要：阶乘末尾非零数求和
Time Limit:1s Memory Limit:1000k
Total Submit:4730 Accepted:1336
下载样例程序(PE)
下载样例程序(ELF)
--------------------------------------------------------------------------------
Problem
对于小于25000的自然数n,求阶乘n!,(n-1)!,(n-2)!...3!,2!,1!右边的非零数之和。
例如：
当n=5时，
5!=120,右边非零数为2;
4!=24,右边非零数为4;
3!=6,右边非零数为6;
2!=2,右边非零数为2;
1!=1,右边非零数为1。
其右边的非零数之和为15。
Input
本题有多组数据，每组数据包含一个正整数N(N不大于25000)占一行。
Output
对给定的每组输入数据，输出一个整数。每个结果占一行。不要输出额外的空行。
Sample Input
5
10
1
Sample Output
15
39
1
#include<iostream.h>
int deal(int n,int &bn)
/*n为待处理的数，处理的结果是先去除尾部所有0，然后去掉2或5的因子
*bn返回因子2的个数减因子5的个数
*函数返回去掉这些因子的n
*/
{
while(n%10==0)n/=10;
if(!(n&1))
do{n>>=1;++bn;}
......