ACM一道题 poj3523 UVA1601双向广度优先BFS

1个回答

#include
#include
#include
#include
using namespace std;

const int maxs = 20;
const int maxn = 150; // 75% cells plus 2 fake nodes
const int dx[]= {1,-1,0,0,0}; // 4 moves, plus "no move"
const int dy[]= {0,0,1,-1,0};

inline int ID(int a, int b, int c)
{
return (a<<16)|(b<<8)|c;
}

int s[3], t[3]; // starting/ending position of each ghost

int deg[maxn], G[maxn][5]; // target cells for each move (including "no move")

inline bool conflict(int a, int b, int a2, int b2)
{
return a2 == b2 || (a2 == b && b2 == a);
}

int d[maxn][maxn][maxn]; // distance from starting state

int bfs()
{
queue q;
memset(d, -1, sizeof(d));
q.push(ID(s[0], s[1], s[2])); // starting node
d[s[0]][s[1]][s[2]] = 0;
while(!q.empty())
{
int u = q.front();
q.pop();
int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff;
if(a == t[0] && b == t[1] && c == t[2]) return d[a][b][c]; // solution found
for(int i = 0; i < deg[a]; i++)
{
int a2 = G[a][i];
for(int j = 0; j < deg[b]; j++)
{
int b2 = G[b][j];
if(conflict(a, b, a2, b2)) continue;
for(int k = 0; k < deg[c]; k++)
{
int c2 = G[c][k];
if(conflict(a, c, a2, c2)) continue;
if(conflict(b, c, b2, c2)) continue;
if(d[a2][b2][c2] != -1) continue;
d[a2][b2][c2] = d[a][b][c]+1;
q.push(ID(a2, b2, c2));
}
}
}
}
return -1;
}

int main()
{
int w, h, n;

``````while(scanf("%d%d%d\n", &w, &h, &n) == 3 && n)
{
char maze[20][20];
for(int i = 0; i < h; i++)
fgets(maze[i], 20, stdin);

// extract empty cells
int cnt, x[maxn], y[maxn], id[maxs][maxs]; // cnt is the number of empty cells
cnt = 0;
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++)
if(maze[i][j] != '#')
{
x[cnt] = i;
y[cnt] = j;
id[i][j] = cnt;
if(islower(maze[i][j])) s[maze[i][j] - 'a'] = cnt;
else if(isupper(maze[i][j])) t[maze[i][j] - 'A'] = cnt;
cnt++;
}

// build a graph of empty cells
for(int i = 0; i < cnt; i++)
{
deg[i] = 0;
for(int dir = 0; dir < 5; dir++)
{
int nx = x[i]+dx[dir], ny = y[i]+dy[dir];
// "Outermost cells of a map are walls" means we don't need to check out-of-bound
if(maze[nx][ny] != '#') G[i][deg[i]++] = id[nx][ny];
}
}

// add fakes nodes so that in each case we have 3 ghosts. this makes the code shorter
if(n <= 2)
{
deg[cnt] = 1;
G[cnt][0] = cnt;
s[2] = t[2] = cnt++;
}
if(n <= 1)
{
deg[cnt] = 1;
G[cnt][0] = cnt;
s[1] = t[1] = cnt++;
}

printf("%d\n", bfs());
}
return 0;
``````

}

ACM一道题，C语言，已经精疲力竭 求大神找出错误，啊啊啊

ACM一道题一直WA，求大神找错

ACM一道题 求大神给出思路或者代码 谢谢~~~~
Problem Description CZJ的舍友请CZJ吃饭，作为舍友CZJ是不会放过吃穷舍友的机会，但自己身体又不好，不能吃太多也不能吃太少。假设每样食物都有一个饱腹度和价值，请你帮他算下刚好吃饱的情况下最多可以吃他舍友多少钱。 Input 第一行是一个T，代表数据的组数T（T≤100001）。每组两个整数p，y（1≤p≤1000，1≤y≤100），分别表示食物的数量和CZJ的饱腹度。 然后p个数Qpi表示第pi个食物的价值，之后p个数Mpi表示吃第pi个食物得到的饱腹度。（1≤Qpi≤10000，1≤Mpi≤1000）。 Output 对于每一个样例输出CZJ能吃下的最大价值。 Sample Input 1 5 100 11 6 7 5 6 40 50 60 20 30 Sample Output 18 Author SCNU20102200088

C++新人 遇到一道ACM的题 不知问题出在哪里

Periodic Strings A character string is said to have period k if it can be formed by concatenating one or more repetitions of another string of length k. For example, the string "abcabcabcabc" has period 3, since it is formed by 4 repetitions of the string "abc". It also has periods 6 (two repetitions of "abcabc") and 12 (one repetition of "abcabcabcabc"). Write a program to read a character string and determine its smallest period. Input The first line oif the input file will contain a single integer N indicating how many test case that your program will test followed by a blank line. Each test case will contain a single character string of up to 80 non-blank characters. Two consecutive input will separated by a blank line. Output An integer denoting the smallest period of the input string for each input. Two consecutive output are separated by a blank line. Sample Input 1 HoHoHo Sample Output 2 简单说就是输入一个长度不超过80个字符串，输出其最小周期（注意题目有关空行的格式问题） 我WA了五次，渣渣被虐哭囧 下面的是我的代码，求给出反例或指出我的逻辑错误，谢谢 ``` //要多注意细节，多考虑极端情况（注意循环字符中还有相同字符的情况!!!） #include <stdio.h> #include <string.h> int main() { int T,len,i,k,temp,first=1;//T代表测试块的个数,len是字符串长度,temp存储可能的周期值 char str[90]={0};//存储字符串 scanf("%d",&T); while(T--){ temp=0,k=0; scanf("%s",str); len=strlen(str); for(i=1;i<len;i++){ if(str[i]==str[0]){ temp=i; for(k=0;k<temp;k++,i++){ if(str[k]!=str[i]){//反向思维，针对ABABACC的情况 temp=0; i--; break; } if(k!=temp-1&&i==len-1){//主要针对ABCDAB的情况 temp=0; break; } if((k==temp-1)&&(i!=len-1)) k=-1;//始终注意k的自加 } } } if(i==len&&!k)//注意不存在周期的情况！ temp=0; if(first){ printf("%d\n",temp); first=0; } else printf("\n%d\n",temp); } return 0; } ```

http://acm.hpu.edu.cn/problem.php?id=1099这是那道题的网站，绝对安全无毒，小渣渣就是想有哪位大佬给写下代码，谢谢啦

Crystal Ball Factory 最小花费题
Problem Description The Astrologically Clairvoyant Manufacturers (ACM),a pioneer in future-predicting technology, just landed a contract to manufacture crystal balls for weather forecasters around the world. Every week, a variable number of crystal balls needs to be delivered; the required amount for each week is specified in the contract. Crystal balls are made from the highest-quality crystal, whose price fluctuates from week to week. Fortunately, the ACM is able to foresee the price of crystal for the coming weeks, thanks to its own future-predicting technology. When the price is low, the ACM would like to buy crystal and manufacture crystal balls, storing any excess in their warehouse. On the other hand, in weeks for which the price is high, ACM would rather use the crystal balls stored in the warehouse to satisfy the demand specified in their contract. However, since there is a also a fixed weekly cost to store each crystal ball in the warehouse, and an initial cost for turning on the manufacturing machines and producing a non-zero quantity of crystal balls, the decision is not always simple. Can you help them fulfill their contract at minimal cost? Input The first line of each test case (representing a contract) will contain the number of weeks for which the contract will last. The next line will contain the non-negative integers b, k and n, where b is the base cost for manufacturing a non-zero quantity of crystal balls on a given week, k is the cost for storing each crystal ball in the warehouse for a week, and n is the maximum capacity of the warehouse. The following lines will describe the weeks specified in the contract in chronological order. Each week is described by a single line which will contain a pair of non-negative integers c and r, where c is the cost for manufacturing a new crystal ball using new crystal bought this week, and r is the number of crystal balls which must be delivered this week. A crystal ball can be manufactured and delivered in the same week if appropriate, in which case it won’t need to be stored in the warehouse at all. The last line of the input will contain the integer 0 and should not be processed. Output For each test case, output the minimum amount which the ACM will have to spend in order to fulfill the entire contract. All the numbers in the input will be at most 1000. Sample Input 4 1 0 1000 1 1 12 4 1 0 1000 1000 2 0 100 1 1 1000 1000 101 0 Sample Output 1007 101101

http://acm.nyist.net/JudgeOnline/problem.php?pid=75 #include<iostream> using namespace std; int n; void data(int y,int m,int d) { switch(m) { case 2: n=31+d; break; case 3: n=59+d; break; case 4: n=90+d; break; case 5: n=120+d; break; case 6: n=151+d; break; case 7: n=181+d; break; case 8: n=212+d; break; case 9: n=242+d; break; case 10: n=272+d; break; case 11: n=303+d; break; case 12: n=334+d; break; } } int main() { int N; cin>>N; for(int i=0;i<N;i++) { int n1=0; int y,m,d; cin>>y>>m>>d; if(m==1) { cout<<d<<endl; } if((n%4 ==0 && n%100 != 0)||n%400 == 0) { data(y,m,d); n1=n; cout<<n1+1<<endl; } else { data(y,m,d); n1=n; cout<<n1<<endl; } } return 0; }

【题目描述】 FFF团成员自带这样一个属性：凭空变出火把与汽油，两者配合起来才能让FFF之火duang的一下烧起来，但是不同的火把与不同的汽油配合产生的火焰是不同的，现在有n种火把与n种汽油，已知每一种火把与每一种汽油配合时产生的火焰的旺盛程度，现在求怎样使得火把与汽油一一配对，产生最旺盛的火焰。 【输入】 第一行为一个整数T，表示有T组数据 每组数据第一行为一个正整数n（2≤n≤30） 第二行开始一共有n行，每行为n个正整数，第i行第j个数表示第i种火把与第j种汽油配合的火焰的旺盛程度。(0<a[i][j]≤10000) 【输出】 每组数据输出一个整数，表示最大的火焰旺盛程度 【样例输入】 2 3 5 2 6 6 7 9 7 4 1 4 8 5 2 8 5 8 2 1 9 6 3 7 7 5 8 1 【样例输出】 20 33 求大神们解答！！谢谢！！
Simulation? 模拟的问题
Problem Description A computer simulation, a computer model, or a computational model is a computer program, or network of computers, that attempts to simulate an abstract model of a particular system. Computer simulations have become a useful part of mathematical modeling of many natural systems in physics, astrophysics, chemistry and biology, human systems in economics, psychology, social science, and engineering, of course, also computer. “Fundamentals of compiling” is an important course for computer science students. In this course, most of us are asked to write a compiler to simulate how a programming language executes. Today, boring iSea invites a new programming language, whose name is Abnormal Cute Micro (ACM) language, and, YOU are assigned the task to write a compiler for it. ACM language only contains two kinds of variables and a few kinds of operations or functions, and here are some BNF-like rules for ACM. Also, here is some explanation for these rules: 1) In ACM expressions, use exactly one blank to separate variables and operators, and as the rule indicates, the operator should apply right to left, for example, the result of “1 - 2 - 3" should be 2. 2) In the build function, use exactly one blank to separate integers, too. 3) Beside there are brackets in function, no other bracket exists. 4) All the variables are conformable, and never exceed 10000. Given an ACM expression, your task is output its value. If the result is a integer, just report it, otherwise report an array using the format “{integer_0, integer_1, … , integer_n}”. Input The first line contains a single integer T, indicating the number of test cases. Each test case includes a string indicating an valid ACM expression you have to process. Technical Specification 1. 1 <= T <= 100 2. 1 <= |S| <= 100, |S| indicating the length of the string. Output For each test case, output the case number first, then the result variable. Sample Input 10 1 + 1 1 - 2 - 3 dance(3) vary(2) * 2 vary(sum(dance(5) - 1)) dance(dance(-3)) 1 - 2 - 3 * vary(dull(build(1 2 3))) dance(dance(dance(dance(dance(2))))) sum(vary(100)) - sum(build(3038)) build(sum(vary(2)) dull(build(1 0)) 2 dull(dance(2))) - build(1 1 1 1) Sample Output Case 1: 2 Case 2: 2 Case 3: {3, -2, 1} Case 4: {2, 4} Case 5: {2, 1} Case 6: -4 Case 7: {2, 5} Case 8: {4, -3, 2, -1} Case 9: 2012 Case 10: {2, 0, 1, 2}

![图片说明](https://img-ask.csdn.net/upload/201911/20/1574224115_275862.png) 如图 我本来想用string转char型数组 然后用每个字母的ascii码计算单词里每个字母出现的次数 但是我做不出来 这样的想法好吗 其他的解法也行 用c++书写 谢谢各位了

Problem Description 网上流传一句话:"常在网上飘啊，哪能不挨刀啊～"。其实要想能安安心心地上网其实也不难，学点安全知识就可以。 首先，我们就要设置一个安全的密码。那什么样的密码才叫安全的呢？一般来说一个比较安全的密码至少应该满足下面两个条件： (1).密码长度大于等于8，且不要超过16。 (2).密码中的字符应该来自下面“字符类别”中四组中的至少三组。 这四个字符类别分别为： 1.大写字母：A,B,C...Z; 2.小写字母：a,b,c...z; 3.数字：0,1,2...9; 4.特殊符号：~,!,@,#,\$,%,^; 给你一个密码，你的任务就是判断它是不是一个安全的密码。 Input 输入数据第一行包含一个数M，接下有M行，每行一个密码（长度最大可能为50），密码仅包括上面的四类字符。 Output 对于每个测试实例，判断这个密码是不是一个安全的密码，是的话输出YES，否则输出NO。 Sample Input 3 a1b2c3d4 Linle@ACM ^~^@^@!% Sample Output NO YES NO

Java学习的正确打开方式

linux系列之常用运维命令整理笔录

Python十大装B语法
Python 是一种代表简单思想的语言，其语法相对简单，很容易上手。不过，如果就此小视 Python 语法的精妙和深邃，那就大错特错了。本文精心筛选了最能展现 Python 语法之精妙的十个知识点，并附上详细的实例代码。如能在实战中融会贯通、灵活使用，必将使代码更为精炼、高效，同时也会极大提升代码B格，使之看上去更老练，读起来更优雅。 1. for - else 什么？不是 if 和 else 才

2019年11月中国大陆编程语言排行榜
2019年11月2日，我统计了某招聘网站，获得有效程序员招聘数据9万条。针对招聘信息，提取编程语言关键字，并统计如下： 编程语言比例 rank pl_ percentage 1 java 33.62% 2 c/c++ 16.42% 3 c_sharp 12.82% 4 javascript 12.31% 5 python 7.93% 6 go 7.25% 7

SQL-小白最佳入门sql查询一

【图解经典算法题】如何用一行代码解决约瑟夫环问题

“狗屁不通文章生成器”登顶GitHub热榜，分分钟写出万字形式主义大作

IT界知名的程序员曾说：对于那些月薪三万以下，自称IT工程师的码农们，其实我们从来没有把他们归为我们IT工程师的队伍。他们虽然总是以IT工程师自居，但只是他们一厢情愿罢了。 此话一出，不知激起了多少(码农)程序员的愤怒，却又无可奈何，于是码农问程序员。 码农：你知道get和post请求到底有什么区别？ 程序员：你看这篇就知道了。 码农：你月薪三万了？ 程序员：嗯。 码农：你是怎么做到的? 程序员：
《程序人生》系列-这个程序员只用了20行代码就拿了冠军

11月8日，由中国信息通信研究院、中国通信标准化协会、中国互联网协会、可信区块链推进计划联合主办，科技行者协办的2019可信区块链峰会将在北京悠唐皇冠假日酒店开幕。 　　区块链技术被认为是继蒸汽机、电力、互联网之后，下一代颠覆性的核心技术。如果说蒸汽机释放了人类的生产力，电力解决了人类基本的生活需求，互联网彻底改变了信息传递的方式，区块链作为构造信任的技术有重要的价值。 　　1

【技巧总结】位运算装逼指南

8年经验面试官详解 Java 面试秘诀
作者 | 胡书敏 责编 | 刘静 出品 | CSDN（ID：CSDNnews） 本人目前在一家知名外企担任架构师，而且最近八年来，在多家外企和互联网公司担任Java技术面试官，前后累计面试了有两三百位候选人。在本文里，就将结合本人的面试经验，针对Java初学者、Java初级开发和Java开发，给出若干准备简历和准备面试的建议。   Java程序员准备和投递简历的实

1.两种思维方式在求职面试中，经常会考察这种问题：北京有多少量特斯拉汽车？ 某胡同口的煎饼摊一年能卖出多少个煎饼？ 深圳有多少个产品经理？ 一辆公交车里能装下多少个乒乓球？ 一