|
|
//考察点: 纯模拟 //思路: 大概听别人说过解题的方向 //提交情况: 2WA 1AC 第一次错在 两个case之间没有空格(实际上应该有) 第二次错在 最后一个case多了一个回车(实际上应该没有) //收获: 对枚举更加熟悉了 //经验: 写完代码仍然需要静态观察 纠结很久的代码需要静下心来一个个模块严重 //ACcode:
//终于AC 啊啊啊啊啊啊
#include<stdio.h>
#include<string.h>
#include<memory.h>
char a[5][30] = {
{'#','-','#','#',' ','#','#','-','#','#','-','#','#',' ','#','#','-','#','#','-','#','#','-','#','#','-','#','#','-','#'},
{'|',' ','|','#',' ','|','#',' ','|','#',' ','|','|',' ','|','|',' ','#','|',' ','#','#',' ','|','|',' ','|','|',' ','|'},
{'#',' ','#','#',' ','#','#','-','#','#','-','#','#','-','#','#','-','#','#','-','#','#',' ','#','#','-','#','#','-','#'},
{'|',' ','|','#',' ','|','|',' ','#','#',' ','|','#',' ','|','#',' ','|','|',' ','|','#',' ','|','|',' ','|','#',' ','|'},
{'#','-','#','#',' ','#','#','-','#','#','-','#','#',' ','#','#','-','#','#','-','#','#',' ','#','#','-','#','#','-','#'}};
void output(int size,char t[])
{
int cnt,i,j,k,tt,mark,len=strlen(t),n=0;
char *p = t;
while(*p)
{
*p -= '0';
p++;
}
for(i=0;i<5;i++)
{
if(i%2 == 0) //even
{
for(cnt=3*t[n];n<len;cnt=3*t[++n])
{
for(j=cnt,mark = cnt;j<cnt+3;j++)
{
if(a[i][j] == '#') printf(" ");
else for(k=0;k<size;k++) printf("%c",a[i][j]);
if(j == mark+2 && n != len-1) printf(" ");
}
}
n=0;
printf("\n");
}
else //odd
{
for(tt=0;tt<size;++tt)
{
for(cnt=3*t[n];n<len;cnt=3*t[++n])
{
for(j=cnt,mark=cnt;j<cnt+3;j++)
{
if(a[i][j] == '#') printf(" ");
else if(a[i][j] == '|') {printf("|");}
else for(k=0;k<size;k++) printf("%c",a[i][j]);
if(j == mark+2 && n != len-1) printf(" ");
}
}
n=0;
printf("\n");
}
}
}
}
int main()
{
int n;
char tmp[11];
while(1)
{
scanf("%d %s",&n,tmp);
if(n == 0 && !strcmp(tmp,"0")) break;
output(n,tmp);
printf("\n");
memset(tmp,0,sizeof(tmp));
}
return 0;
}
//special thanks to : http://hi.baidu.com/elliott_hdu/blog/item/9841f0a8c8b004b4cb130cf3.html
//考察点: 字符串的处理
//思路: 要求判定题目中描述的 surprising string . 用到了一个类似枚举的方法 按照题意直接模拟解决问题
//收获: 学习到了一种记忆以前状态的方法 做成数组的方式来判定是不是在枚举的过程中曾经出现过.
//经验: 类似字符串处理的题目经常跟下标的确定有很大的关系, 往往数组的下标可以造成很大的差异 并且枚举数据的时候边界也很不好确定. 这些都需要在写程序之前想好.
//ACcode:
#include<stdio.h>
#include<string.h>
#include<memory.h>
char a[80];
int rec[30][30];
bool judge()
{
int len,i,j;
len = strlen(a);
if(len <= 2) return true;
memset(rec,-1,sizeof(rec));
for(i=0;i<=len-2;i++) //枚举从长度0一直到len-2 这是根据题目的意思 联系KMP算法 第一层的时候也是枚举 长度
for(j=0;j<len-i-1;j++) //这里是总长度去掉 枚举出的长度i 也就是 len-i-2(长度i的边界的两个数字(不包含在长度i中))+1 = len-i-1;
{
if(rec[a[j]-'A'][a[j+i+1]-'A'] == i) return false;
else rec[a[j]-'A'][a[j+i+1]-'A'] = i;
}
return true;
}
int main()
{
//freopen("pku_3096_in.txt","r",stdin);
while(scanf("%s",a))
{
if(strcmp(a,"*")==0) break;
if(judge())
printf("%s is surprising.\n",a);
else
printf("%s is NOT surprising.\n",a);
}
return 0;
}
//考察点: 简单dfs
//思路: 这个题目可以用dfs做也可用bfs做 但是bfs还没有想到怎么做. 在dfs的过程中就能顺便计算出周长(perimeter) 像类似这样的题目非常像走迷宫类型. 因为需要求解的是最终的周长 发现一个性质 如果某个X跟其他的X相邻的话,相邻处就要扣掉一条边(初始perimeter is 4) 于是利用深搜找到所有的可能.
//提交情况 3WA 2AC
WA 因为 技术变量 i,j 位置没有放对 最好不要开成全局的 否则会出现莫名其妙的错误.
//收获: 第一次接触dfs. 知道dfs是利用递归的思路来做的 只要子问题跟原问题的性质相同 递归就能发挥作用.
//经验: 写递归程序的时候可以把之后的问题看成是子问题 于是处理好程序出口以后就可以直接调用自己了.
//AC code
#include<stdio.h>
#include<memory.h>
#define maxn 21
char a[maxn][maxn];
bool c[maxn][maxn];
int e[8][2]={{-1,1},{0,1},{1,1},{-1,0},{1,0},{-1,-1},{0,-1},{1,-1}};
int f[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int sum;
int n,m,p,q;
void dfs(int p1,int q1)
{
int i,j;
for(i=0;i<8;i++)
{
int pp = p1 + e[i][0];
int qq = q1 + e[i][1];
if(pp<0||pp>=n||qq<0||qq>=m) continue;
if(a[pp][qq] == '.') continue;
if(c[pp][qq] == 1) continue;
for(j=0;j<4;j++)
{
int x = pp + f[j][0];
int y = qq + f[j][1];
if(x<0||x>=n||y<0||y>=m) {sum++;continue;}
if(c[x][y] == true)
{
sum--;
continue;
}
else
{
sum++;
continue;
}
}
c[pp][qq] = true;
dfs(pp,qq);
}
}
int main()
{
int i;
//freopen("pku_1111_in.txt","r",stdin);
while(1)
{
scanf("%d%d%d%d",&n,&m,&p,&q);
if(n+m+p+q == 0) break;
for(i=0;i<n;i++)
scanf("%s",a[i]);
p-=1,q-=1;
if(a[p][q] == '.') {printf("0\n");continue;}
memset(c,0,sizeof(c));
sum = 4;
c[p][q] = true;
dfs(p,q);
printf("%d\n",sum);
}
return 0;
}
 /*
Sourse: http://cdy20.bokee.com/viewdiary.41014871.html
Name: Floyd-Warshall poj 1125
Copyright: cdy20
Author: cdy20
Date: 29-07-08 16:38
Description: Floyd-Warshall 复杂度O(n^3)
本题目求那个中转者发信息给其他所有人 的时间最快
特别注意：一个人发信息给其他人，最快完成这项工作所需的时间
由时间花费最长那个决定
总结：floyd其实都是根据那两个定理变化，虽然那两个定理比较傻b
（一看就知道，刚开始还奇怪，一看就知道的定理有什么用，
现在发现，sb的一看就知道的定理可以变化成一个算法，几个定理解决一个问题）
定理（大概）：
1.任何两点i,j之间的路径若通过第三个点v,
则此时i,v之间,v,j之间所连路径也是最短的.
a[i][j]最短-->a[i][v],a[v][j]最短 (v为最短路径i-j经过的点)
2.若i,j之间的路径比i,v之间,v,j之间路径的和大则i,j之间最短路径不大于i,v之间,
v,j之间路径的和.
a[i][j]=min(a[i][j],a[i][k] a[k][j]);（这是在程序过程中，不断更新的）
*/
//考察点: floyd //思路: 利用floyd求出任意两点之间的最短时间(存放在数组a[i][j]中) 找出a[i][j]中的最大值就是通知所有人所需要的最短时间(a[i][j]中的某一个值代表通知某人需要的最短时间,因此任意两个人之间通知的最短时间已知 找到所有最短时间的最大值就是信息散布给所有人时的最坏情况 也就是说 当整个网络中最慢被通知到的人都被通知到了,有理由相信所有人都可以在这个时间内被通知到) 于是先用floyd求出任意两点之间的长度 然后找到最大值 如果找不到就输出 disjoint //提交情况: 1AC 主要是在设置maxint的时候出错了 原来(错误的状态是): const int INF = 1 << 30; 正确的设置方法应该是 const int INF = 0xfffffff; //收获: 应用了一次floyd算法 初步熟悉了该算法 学会了怎么找到最小 学会了怎样写 "没有找到希望的值" //经验: 写好代码以后要观察 时刻注意变量是不是需要初始化 //AC code
#include<stdio.h>
#include<memory.h>
#include<iostream>
#define MAX 101
using namespace std;
const int INF = 0xfffffff;
int a[101][101];
int main()
{
int n,m,i,j,k;
int tmp,val;
while(1)
{
for(i=1;i<=100;i++)
for(j=1;j<=100;j++)
a[i][j] = INF;
scanf("%d",&n);
if(n == 0) break;
for(i=1;i<=n;i++)
{
a[i][i] = 0;
scanf("%d",&m);
for(j=0;j<m;j++)
{
scanf("%d%d",&tmp,&val);
a[i][tmp] = val;
}
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
a[i][j] = min(a[i][j],a[i][k]+a[k][j]);
}
val = -1;
int ans = INF;
for(i=1;i<=n;i++)
{
tmp = -1;
for(j=1;j<=n;j++)
{
tmp = max(tmp,a[i][j]);
}
if(tmp < ans) {ans = tmp;val = i;}
}
if(val == -1) printf("disjoint\n");
else printf("%d %d\n",val,ans);
}
return 0;
}
首先要了解KMP算法中的next[]和nextval[]。
nexttval[]算是next[]的改进算法，不过就是s[k]、s[j]是否相等的区别。
我的理解是，假设a是源字符串，b是要进行匹配的字串，next[i]及nextval[]通过b串生成。i指向a串当前进行匹配的字符，j指向b串当前进行匹配的字符。
规定，next[]与nextval[]第一个元素的值为字符串起始元素序号减1。
next[j]是当b[j]失配（即a[i]!=b[j]）时，j往前跳的位置。能保证：b[0]到b[j-1]均与a[i]前j-1个字符（不包括a[i]本身）一一匹配；且此时next[j]能保证b[0]到b[next[j]-1]均与a[i]前next[j]-1个字符（不包括a[i]本身）一一匹配的，小于j的最大值。
nextval[i]与next[i]一样，只不过，b[j]有可能等于b[next[j]]，所以失配后，用next[]可能要跳几次才能找到a[i]与b[j]不同的值继续匹配；而b[j]不会等于b[nextval[j]]，所以失配后只需跳一次即可。
比如：
| |
a |
a |
a |
a |
b |
b |
| j |
0 |
1 |
2 |
3 |
4 |
5 |
| next[] |
-1 |
0 |
1 |
2 |
3 |
0 |
| nextval[] |
-1 |
-1 |
-1 |
-1 |
3 |
0 |
| |
a |
b |
c |
a |
b |
d |
a |
b |
c |
a |
b |
d |
| j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
| next[] |
-1 |
0 |
0 |
0 |
1 |
2 |
0 |
1 |
2 |
3 |
4 |
5 |
| nextval[] |
-1 |
0 |
0 |
-1 |
0 |
2 |
-1 |
0 |
0 |
-1 |
0 |
2 |
应该讲得差不多了吧。下面是KMP算法的模板：
生成next[]的模板：（s为传入的字符串，l为s的长度，next[]为要生成的next数组；如果是string类型，则将“char s[]”改为“string s”即可）
void getNext(char s[],int len,int next[])
{ int i,k; i=0; k=-1;
next[0] = -1;
while(i < len)
{ if (k==-1 || s[i]==s[k])
{
k++; i++;
next[i]=k;
}
else k=next[k];
}
}
生成nextval[]的模板：（s为传入的字符串，l为s的长度，nextval[]为要生成的nextval数组；如果是string类型，则将“char s[]”改为“string s”即可）
void getNextVal(char s[],int len,int nextval[])
{ int i,k; i=0; k=-1;
nextval[0] = -1;
while(i < len)
{
if(k == -1 || s[i] == s[k])
{ k++; i++;
if(s[i] != s[k])
nextval[i] = k;
else nextval[i] = nextval[k];
}
else
k=nextval[k];
}
}
具体使用的实例：
1、POJ 2406 Power Strings
题意：给一个字符串S长度不超过10^6，求最大的n使得S由n个相同的字符串a连接而成，如："ababab"则由n=3个"ab"连接而成，
"aaaa"由n=4个"a"连接而成，"abcd"则由n=1个"abcd"连接而成。
定理：假设S的长度为len，则S存在循环子串，当且仅当，len可以被len - next[len]整除，最短循环子串为S[len - next[len]]
例子证明：
设S=q1q2q3q4q5q6q7q8，并设next[8] = 6，此时str = S[len - next[len]] = q1q2，
由字符串特征向量next的定义可知，q1q2q3q4q5q6 = q3q4q5q6q7q8，
即有q1q2＝q3q4，q3q4＝q5q6，q5q6＝q7q8，即q1q2为循环子串，且易知为最短循环子串。
由以上过程可知，若len可以被len - next[len]整除，则S存在循环子串，否则不存在。
解法：利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，
则最大循环次数n为len/(len - next[len])，否则为1。
2、POJ 3461 Oulipo
下面是 m^n % k 的快速幂：
// m^n % k
int quickpow(int m,int n,int k)
{
int b = 1;
while (n > 0)
{
if (n & 1)
b = (b*m)%k;
n = n >> 1 ;
m = (m*m)%k;
}
return b;
}
下面是矩阵快速幂：
//HOJ 3493
/*===================================*/
|| 快速幂（quickpow）模板
|| P 为等比，I 为单位矩阵
|| MAX 要初始化！！！！
||
/*===================================*/
/*****************************************************/
#include <cstdio>
const int MAX = 3;
typedef struct{
int m[MAX][MAX];
} Matrix;
Matrix P = {5,-7,4,
1,0,0,
0,1,0,
};
Matrix I = {1,0,0,
0,1,0,
0,0,1,
};
Matrix matrixmul(Matrix a,Matrix b) //矩阵乘法
{
int i,j,k;
Matrix c;
for (i = 0 ; i < MAX; i++)
for (j = 0; j < MAX;j++)
{
c.m[i][j] = 0;
for (k = 0; k < MAX; k++)
c.m[i][j] += (a.m[i][k] * b.m[k][j])%9997;
c.m[i][j] %= 9997;
}
return c;
}
Matrix quickpow(long long n)
{
Matrix m = P, b = I;
while (n >= 1)
{
if (n & 1)
b = matrixmul(b,m);
n = n >> 1;
m = matrixmul(m,m);
}
return b;
}
/*************************************/
int main()
{
Matrix re;
int f[3] = {2,6,19};
long long n;
while (scanf("%I64d",&n) && n != 0)
{
if (n == 1)
printf("1\n");
else if (n <= 4)
printf("%d\n",f[n-2]);
else {
re = quickpow(n - 4);
printf("%d\n",(((re.m[0][0]*f[2])
+ (re.m[0][1]*f[1]) + (re.m[0][2]*f[0])) %9997 + 9997) % 9997);
}
}
return 0;
}
摘要: Mayor's posters
Description
The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. ... 阅读全文
Calculator
Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 369 Accepted Submission(s): 119
Problem Description
Golden Adobe is the most advanced computer for scientific computing in the world. Unfortunately, it broke down. Your task is to write a super computing software to take its place. The software contains 10 registers named from A to J. There are three operations on the registers:
1) Assignment: X=Y
2) Addition: X+=Y
3) Multiplication: X*=Y
Notice that X and Y are two registers, and they may be the same.
Initially, all the registers are stored by integer 1. Your program should operate several operations and output the final result for 10 registers. You may assume that the length of each decimal number stored in the register is no longer than 5000.
Input
The input contains only one test case including several lines.
Each line contains an operation to be calculated.
The number of operations will no more than 300000.
Output
The output should contains exactly 10 lines, each line contains an integer denoting the decimal number in the register. See sample test case for further details.
Sample Input
A+=B
A*=A
A+=A
B+=A
C+=B
D=B
Sample Output
8
9
10
9
1
1
1
1
1
1
读入注意要用Scanner中的next()方法，用nextline()就TLE
 import java.math.*;
import java.util.*;
  public class Main  {
 public static BigInteger[] num = new BigInteger[10];;
  public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
for (int i = 0; i < 10; i++) {
num[i] = BigInteger.ONE;
 }
while (cin.hasNext()) {
String s = cin.next();
if (s.length() == 4) {
if (s.charAt(1) == '*') {
num[s.charAt(0) - 'A'] = num[s.charAt(0) - 'A'].multiply(num[s.charAt(3) - 'A']);
} else {
num[s.charAt(0) - 'A'] = num[s.charAt(0) - 'A'].add(num[s.charAt(3) - 'A']);
}
} else {
num[s.charAt(0) - 'A'] = num[s.charAt(2) - 'A'];
}
}
for (int i = 0; i < 10; i++) {
System.out.println(num[i]);
}
}
 }
N!
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 17754 Accepted Submission(s): 4605
Problem Description
Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!
Input
One N in one line, process to the end of file.
Output
For each N, output N! in one line.
Sample Input
1
2
3
Sample Output
1
2
6
Java解高精度的题目还是很爽的，注意类名要写成Main， Compilation Error了n次。
import java.math.*;
import java.util.*;
public class Main {
public static BigInteger num;
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
num = BigInteger.ONE;
int n = cin.nextInt();
num = BigInteger.ONE;
for (int i = 1; i <= n; i++) {
num= num.multiply(BigInteger.valueOf(i));
}
System.out.println(num);
}
}
}
匈牙利算法：
//poj_1469
/*==================================================*\
| 二分图匹配（匈牙利算法DFS 实现）
| INIT: g[][]邻接矩阵;
| 优点：实现简洁容易理解，适用于稠密图，DFS找增广路快。
| 找一条增广路的复杂度为O（E），最多找V条增广路，故时间复杂度为O（VE）
\*==================================================*/
#include <cstdio>
#include <memory.h>
bool g[110][310],flag,vis[310];
int match[310];
int p,n;
/************* 匈牙利算法**************/
int SearchPath(int u)
{
for (int v = 1; v <= n; v ++)
if (g[u][v] && ! vis[v])
{
vis[v] = true;
if (match[v] == -1 || SearchPath(match[v]))
{
match[v] = u;
return 1;
}
}
return 0;
}
/**********************************/
int main()
{
int i,j,k,t,v,cnt;
scanf("%d",&t);
while (t--)
{
scanf("%d %d", &p, &n);
for (i = 1; i <= p; i++)
for (j = 1; j <= n; j++)
g[i][j] = false;
for (i = 1; i <= n; i++)
match[i] = -1;
flag = true;
for (i = 1; i <= p; i++)
{
scanf("%d",&k);
if (k == 0)
flag = false;
while (k--)
{
scanf("%d",&v);
g[i][v] = true;
}
}
if (flag)
{
cnt = 0;
for (i = 1; i <= p; i++)
{
/***************/
memset(vis,false,sizeof(vis));
cnt += SearchPath(i);
/*********************************/
}
if (cnt == p)
printf("YES\n");
else printf("NO\n");
}
else printf("NO\n");
}
return 0;
}
//poj_1469
/*==================================================*\
| 二分图匹配（Hopcroft－Carp 的算法）
| INIT: g[][]邻接矩阵;
| CALL: res = MaxMatch(); Nx, Ny要初始化！！！
| Mx，My为match
| 时间复杂度为O（V^0.5 E）
\*==================================================*/
/***********************Hopcroft－Carp 算法****************************************/
#include <cstdio>
#include <memory.h>
#include <queue>
using namespace std;
const int MAXN = 310;
const int INF = 1 << 28;
bool flag;
int p,n;
int Mx[MAXN], My[MAXN], Nx, Ny;
int dx[MAXN], dy[MAXN], dis;
bool vst[MAXN],g[110][310];
bool searchP(void)
{
queue <int> Q;
dis = INF;
memset(dx, -1, sizeof(dx));
memset(dy, -1, sizeof(dy));
for (int i = 1; i <= Nx; i++)
if (Mx[i] == -1){
Q.push(i); dx[i] = 0;
}
while (!Q.empty()) {
int u = Q.front(); Q.pop();
if (dx[u] > dis) break;
for (int v = 1; v <= Ny; v++)
if (g[u][v] && dy[v] == -1) {
dy[v] = dx[u]+1;
if (My[v] == -1) dis = dy[v];
else{
dx[My[v]] = dy[v]+1;
Q.push(My[v]);
}
}
}
return dis != INF;
}
bool DFS(int u){
for (int v = 1; v <= Ny; v++)
if (!vst[v] && g[u][v] && dy[v] == dx[u]+1) {
vst[v] = 1;
if (My[v] != -1 && dy[v] == dis) continue;
if (My[v] == -1 || DFS(My[v])) {
My[v] = u; Mx[u] = v;
return 1;
}
}
return 0;
}
int MaxMatch(void){
int res = 0;
memset(Mx, -1, sizeof(Mx));
memset(My, -1, sizeof(My));
while (searchP()) {
memset(vst, 0, sizeof(vst));
for (int i = 1; i <= Nx; i++)
if (Mx[i] == -1 && DFS(i)) res++;
}
return res;
}
/**********************************************************************/
int main()
{
int i,j,k,t,v,cnt;
scanf("%d",&t);
while (t--)
{
scanf("%d %d", &p, &n);
for (i = 1; i <= p; i++)
for (j = 1; j <= n; j++)
g[i][j] = false;
flag = true;
for (i = 1; i <= p; i++)
{
scanf("%d",&k);
if (k == 0)
flag = false;
while (k--)
{
scanf("%d",&v);
g[i][v] = true;
}
}
Nx = p; Ny = n;
if (flag)
{
cnt = MaxMatch();
if (cnt == p)
printf("YES\n");
else printf("NO\n");
}
else printf("NO\n");
}
return 0;
}
|