liuchuo / pat Goto Github PK
View Code? Open in Web Editor NEW🍭 浙江大学PAT题解(C/C++/Java/Python) - 努力成为萌萌的程序媛~
🍭 浙江大学PAT题解(C/C++/Java/Python) - 努力成为萌萌的程序媛~
1042 Shuffling Machine (20)(20 分)
洗牌的时候回写数据会消耗额外的时间吧。
int cards[2][55];
int *from = cards[0], *to = cards[1];
………………
for (int t = times; t > 0; t--) {
for (int i = 1; i <= 54; i++) {
to[rules[i]] = from[i];
}
swap(from,to);
}
只要交换from,to就可以吧
卡了一天的一道题,最后还是你的博客救了我,谢谢学姐分享解题思路
PS:如果可以的话,我也想求认识 哈
我想问下那个题的算法是如何实现的,虽然有注释,但还是有的地方看不懂。。。
long long int *a = new long long int [n];
Dynamic allocated array a[]
has not been freed with delete []
, which may not supposed to be a good habit:(
for(int i = 0; i < k; i++) { //Kmax=n
fill(visit, visit + 1010, false);
scanf("%d", &a);
int cnt = 0;
visit[a] = true;
for(int j = 1; j <= n; j++) { //Jmax=n
if(visit[j] == false) {
dfs(j); //dfs是O(n^2)
cnt++;
}
}
printf("%d\n", cnt - 1);
}
你觉得呢?
您好,在您的博客1028题解中
我认为有个bug。
题目要求在名字和成绩相同的时候,按学号从小到大排序。
但是您的代码中cmp1函数并没有反映出来。
以以下测试为例:
6 2
000007 James 87
000001 James 81
000002 James 82
000003 James 83
000004 James 84
000005 James 85
用您的代码输出结果如图:
您好:
在A-1086题中,题目并没有说所有节点的值互不相同。因此,在有多个节点的值相同的情况下,您的代码会输出错误的结果。
虽然一开始,我也是这么写的 : P
例如,测试数据:
测试用例:
19
Push 4
Push 11
Push 7
Push 12
Pop
Pop
Pop
Push 14
Push 17
Pop
Pop
Push 6
Push 18
Pop
Push 8
Pop
Pop
Push 4
Pop
Pop
Push 11
Push 16
Push 11
Push 12
Pop
Push 2
Pop
Pop
Pop
Push 7
Push 4
Pop
Pop
Push 12
Pop
Pop
Push 11
Pop
对应输出应该为:
12 7 17 8 18 4 6 14 11 2 12 11 4 12 7 16 11 11 4
你的输出为:
12 7 17 8 18 6 14 11 11 16 4 7 2 11 12 12 11 4 4
测试数据100001234
正确答案应该是输出yi Yi ling yi Qian er Bai san Shi si
您的代码输出yi Yi yi Qian er Bai san Shi si 少个ling
这是我的解法,也是超时,不知道还有没有优化的空间……求小姐姐帮帮忙……
#include <cstdio>
#include <vector>
#include <algorithm>
#define _HASH(x) (\
(x[0] - 'A') * 26 * 26 * 10 +\
(x[1] - 'A') * 26 * 10 +\
(x[2] - 'A') * 10 +\
(x[3] - '0') \
)
#define _UNHASH(val, str) do {\
str[4] = 0; \
str[3] = val % 10 + '0'; \
str[2] = val % (10 * 26) / 10 + 'A'; \
str[1] = val % (10 * 26 * 26) / (10 * 26) + 'A'; \
str[0] = val / (10 * 26 * 26) + 'A'; \
} while (0)
int main(int argc, char* argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int stuNum, couNum;
scanf("%d%d", &stuNum, &couNum);
getchar();
std::vector<std::vector<int>> Course(couNum + 1, std::vector<int>());
char name[5];
int num, couInd, hashedName;
for (int i=0; i!=stuNum; ++i) {
scanf("%s %d", name, &num);
hashedName = _HASH(name);
for (int j=0; j!=num; ++j) {
scanf("%d", &couInd);
Course[couInd].push_back(hashedName);
} getchar();
}
for (int i=1; i!=couNum + 1; ++i) {
printf("%d %zu\n", i, Course[i].size());
std::sort(Course[i].begin(), Course[i].end());
for (auto j : Course[i]) {
_UNHASH(j, name);
puts(name);
}
}
return 0;
}
1块一个月,这样应该能减轻你的服务器费的负担~
大部分测试用例结尾不输出换行符都可以通过。
只有一个出现格式错误,是由于该测试点为特例,其结果为0。没有换行符其结果只有一行。
不用算连续因子最多不会超过12个。也不需要三重循环,两重循环即可。
直接去计算当前部分乘积能不能整除N。
代码如下:
#include<iostream>
#include<cmath>
using namespace std;
long int num,temp;
int main(){
cin >> num;
int first = 0, len = 0, maxn = sqrt(num);
for (int i = 2; i <= maxn; i++){
int j; temp = 1;
for ( j = i; j <= maxn; j++){
temp *= j;
if (num%temp != 0)break;
}
if (j - i > len){
len = j - i;
first = i;
}
}
if (first == 0)cout << 1 << endl << num;
else {
cout << len << endl;
for (int i = 0; i < len; i++){
cout << first + i;
if (i != len - 1)
cout << '*';
}
}
return 0;
}
程序中的不足点:
这道题考的是DFS+剪枝。
我认为主要剪枝的地方有三个:
1,tempK==K但是tempSum!=n的时候需要剪枝。
2,在枚举的时候,按顺序枚举,上界或者下界可进行剪枝。
3,当且仅当tempSum + v[index] <= n时,进行下一层的DFS,而不要进入下一层DFS发现不满足条件再返回。这样开销会比较大。
修改后的代码如下:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n, k, p, maxFacSum = -1;
vector<int> v, ans, tempAns;
void init() {
int temp = 0, index = 1;
while (temp <= n) {
v.push_back(temp);
temp = pow(index, p);
index++;
}
}
void dfs(int index, int tempSum, int tempK, int facSum) {
if (tempK == k ) {
if (tempSum == n) {
if (facSum > maxFacSum) {
ans = tempAns;
maxFacSum = facSum;
}
}
return;
}
while(index >= 1) {
if (tempSum + v[index] <= n) {
tempAns[tempK] = index;
dfs(index, tempSum + v[index], tempK + 1, facSum + index);
}if (index == 1)
return;
index--;
}
}
int main() {
scanf("%d%d%d", &n, &k, &p);
init(); tempAns.resize(k);
dfs(v.size() - 1, 0, 0, 0);
if (maxFacSum == -1) {
printf("Impossible");
return 0;
}
printf("%d = ", n);
for (int i = 0; i < ans.size(); i++) {
if (i != 0) printf(" + ");
printf("%d^%d", ans[i], p);
}
return 0;
}
但是,经测,您的代码耗时约在900~1000ms之间。
79行minn = j;
好像应该是minn = dis[j];
很早的时候就看到你的博客了,当时我准备考PAT,看了一些你的题解,但是那个寒假也没刷多少题,结果考了20多分,实在是惭愧啊。
不过也没事,我后来也没考浙大,PAT分数也不要紧,反正结果能顺利读研就行了,这次又翻了翻你的博客,也翻了翻你的github,不得不说你真的是一位非常非常优秀的程序媛!!!
你现在应该也毕业了吧,能不能透露下去向,求认识。
一部分代码可以优化一下逻辑,能快那么一丢丢。
来看代码,在您的func1(string s)中的:
cout << b[num / 13];
if((num % 13) && (num / 13)) {
cout << " " << a[num % 13];
} else if(num % 13) {
cout << a[num % 13];
} else if(num == 0) {
cout << a[num % 13];
}
这一部分中,只考虑判断部分,简化一下,看得清楚一点:
#include <iostream>
int main(int argc, char** argv) {
int num=4;
if((num % 13) && (num / 13)) {
num=1 ;
} else if(num % 13) {
num=2;
} else if(num == 0) {
num=3;
}
return 0;
}
那么这段代码,main函数生成的汇编如下(GCC 4.7.2):
0x004013b0 <+0>: push ebp
0x004013b1 <+1>: mov ebp,esp
0x004013b3 <+3>: and esp,0xfffffff0
0x004013b6 <+6>: sub esp,0x10
0x004013b9 <+9>: call 0x40dac0 <__main>
0x004013be <+14>: mov DWORD PTR [esp+0xc],0x3
0x004013c6 <+22>: mov eax,DWORD PTR [esp+0xc]
0x004013ca <+26>: mov ecx,0xd
0x004013cf <+31>: cdq
0x004013d0 <+32>: idiv ecx
0x004013d2 <+34>: mov eax,edx
0x004013d4 <+36>: test eax,eax
0x004013d6 <+38>: je 0x4013ee <main(int, char**)+62>
0x004013d8 <+40>: mov eax,DWORD PTR [esp+0xc]
0x004013dc <+44>: add eax,0xc
0x004013df <+47>: cmp eax,0x18
0x004013e2 <+50>: jbe 0x4013ee <main(int, char**)+62>
0x004013e4 <+52>: mov DWORD PTR [esp+0xc],0x1
0x004013ec <+60>: jmp 0x401419 <main(int, char**)+105>
0x004013ee <+62>: mov eax,DWORD PTR [esp+0xc]
0x004013f2 <+66>: mov ecx,0xd
0x004013f7 <+71>: cdq
0x004013f8 <+72>: idiv ecx
0x004013fa <+74>: mov eax,edx
0x004013fc <+76>: test eax,eax
0x004013fe <+78>: je 0x40140a <main(int, char**)+90>
0x00401400 <+80>: mov DWORD PTR [esp+0xc],0x2
0x00401408 <+88>: jmp 0x401419 <main(int, char**)+105>
0x0040140a <+90>: cmp DWORD PTR [esp+0xc],0x0
0x0040140f <+95>: jne 0x401419 <main(int, char**)+105>
0x00401411 <+97>: mov DWORD PTR [esp+0xc],0x3
0x00401419 <+105>: mov eax,0x0
0x0040141e <+110>: leave
0x0040141f <+111>: ret
但是如果把这段代码改为:
#include <iostream>
int main(int argc, char** argv) {
int temp=4;
if (temp / 13 > 0){
temp=1;
if (temp % 13)
temp=2;
}
else
temp=3;
return 0;
}
对应的汇编如下:
0x004013b0 <+0>: push ebp
0x004013b1 <+1>: mov ebp,esp
0x004013b3 <+3>: and esp,0xfffffff0
0x004013b6 <+6>: sub esp,0x10
0x004013b9 <+9>: call 0x40daa0 <__main>
0x004013be <+14>: mov DWORD PTR [esp+0xc],0x2
0x004013c6 <+22>: cmp DWORD PTR [esp+0xc],0xc
0x004013cb <+27>: jle 0x4013f1 <main(int, char**)+65>
0x004013cd <+29>: mov DWORD PTR [esp+0xc],0x1
0x004013d5 <+37>: mov eax,DWORD PTR [esp+0xc]
0x004013d9 <+41>: mov ecx,0xd
0x004013de <+46>: cdq
0x004013df <+47>: idiv ecx
0x004013e1 <+49>: mov eax,edx
0x004013e3 <+51>: test eax,eax
0x004013e5 <+53>: je 0x4013f9 <main(int, char**)+73>
0x004013e7 <+55>: mov DWORD PTR [esp+0xc],0x2
0x004013ef <+63>: jmp 0x4013f9 <main(int, char**)+73>
0x004013f1 <+65>: mov DWORD PTR [esp+0xc],0x3
0x004013f9 <+73>: mov eax,0x0
0x004013fe <+78>: leave
0x004013ff <+79>: ret
可以看到,逻辑上有点优化。
因此,我建议把代码改为:
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
string a[13] = { "tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct",
"nov", "dec" };
string b[13] = { "", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy",
"lok", "mer", "jou" };
void func1(string s) {
int len = s.length(), num = 0;
for (int i = 0; i < len; i++)
num = num * 10 + (s[i] - '0');
if (num / 13) {
cout << b[num / 13];
if (num % 13)
cout << ' ' << a[num % 13];
}
else
cout << a[num % 13];
}
void func2(string s) {
int len = s.length(), num = 0;
if (len == 4) {
cout << 0;
return;
}
else if (len == 3) {
for (int i = 1; i <= 12; i++) {
if (s == a[i]) {
cout << i;
return;
}
if (s == b[i]) {
cout << i * 13;
return;
}
}
}
else {
string temp1 = s.substr(0, 3), temp2 = s.substr(4, 3);
for (int i = 1; i <= 12; i++) {
if (temp1 == b[i]) num += i * 13;
if (temp2 == a[i]) num += i;
}
cout << num;
}
return;
}
int main() {
int n;
cin >> n;
getchar();
for (int i = 0; i < n; i++) {
string s;
getline(cin, s);
if (isdigit(s[0]))
func1(s);
else
func2(s);
cout << endl;
}
return 0;
}
RTRT
如题,题目中所说的范围在 [-2^63, 2^63],而long long 是不能表示2^63的,long long 的最大取值是2^63-1。
因此,在如下测试中,会出错
1
9223372036854775808 -9223372036854775808 -1
很明显A+B=0>-1,应该输出true,但是结果是false。
乙级1003这道题在vs2017上编译通不过
这句:
if(w[u] + weight[v] > w[v])
w[v] = w[u] + weight[v];
对w[v]的更新是不是太过简单了,如果在这个测试点下:
5 6 0 4
1 2 10 5 3
0 1 2
0 2 3
0 4 6
1 3 2
2 4 3
3 4 2
正确答案是3 21(应该是吧……),但代码给出的结果是3 14。
如果我哪里理解的有问题,请指教QAQ
从你的博客中得到了很大的帮助,也在这里表达一下感谢~
思路分析:
#include<iostream>
using namespace std;
int temp, N, cnt = 0;
bool num[100002] = { 0 };
int main(){
cin >> N;
for (int i = 0; i < N; i++) {
scanf("%d", &temp);
if (temp > N || temp <= 0)
continue;
num[temp] = true;
}
while (++cnt){
if (num[cnt] == false)break;
}
cout << cnt;
return 0;
}
只需要26ms。
为了评论一下我还特地注册了一下GitHub,感觉还蛮有用的(哈哈)。
for(int i = 0; i < s.length(); i++) {
if(s[i] == pre)
cnt++;
else
cnt = 1;
m[s[i]] = (cnt % k == 0);
pre = s[i];
}
本来我是没什么思路,来寻找思路,然后找到了这位妹纸^_^,这一段这里我发觉有点问题,你的这个是只要后面有不是连续的3个,就给m[s[i]]赋值false,拿样例打比方,如果前面都是1个2个s,最后一个单词出现了连续的三个s,按照你的思路,这个s就会被认为是坏的键,从而输出了。
读取时直接将使用build函数数据插入BST。理论依据时什么呢?感觉二叉树的前序遍历不能保证树的唯一性,那么如何保证按照前序插入构造出来的BST一定是原始BST呢?如果不唯一,是否会影响后续红黑树的判定?
如果是确定的,能否提供一下相关的资料?谢谢。
需要添加输入判断。
题目中并没有说明两点之间最多只有一条路。也就是说,有可能两点之间有多条路,因此需要添加判断,只存储距离最短的路。另外,也有可能会出现 G1 G1 9999这样的测试数据,因此,自身与自身之间的距离要初始化为0.
举例说明,以官网的测试数据为例,在最后一行新加一条2 G2 2
为了看着方便,我调整了以下顺序,不影响。也即:
4 3 12 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
2 G2 1
2 G2 2
前11行是测试1,可以看到,2和G2之间,有两条路,因此在求最短路径的时候,要把最短的路保存下来。
代码如下:
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int inf = 999999999;
int n, m, k, ds, station;
int e[1020][1020], dis[1020];
bool visit[1020];
int main() {
fill(e[0], e[0] + 1020 * 1020, inf);
//--------新增代码-------
for (int i = 0; i < 1020; i++){
e[i][i] = 0;
}
//-----------------------
fill(dis, dis + 1020, inf);
scanf("%d%d%d%d", &n, &m, &k, &ds);
string s, t;
for (int i = 0; i < k; i++) {
int tempdis;
cin >> s >> t >> tempdis;
int a, b;
if (s[0] == 'G') {
s = s.substr(1);
a = n + stoi(s);
}
else {
a = stoi(s);
}
if (t[0] == 'G') {
t = t.substr(1);
b = n + stoi(t);
}
else {
b = stoi(t);
}
//----------这里添加了求min-------
e[a][b] = e[b][a] = min(tempdis, e[a][b]);
//--------------------------------
}
int ansid = -1;
double ansdis = -1, ansaver = inf;
for (int index = n + 1; index <= n + m; index++) {
double mindis = inf, aver = 0;
fill(dis, dis + 1020, inf);
fill(visit, visit + 1020, false);
dis[index] = 0;
for (int i = 0; i < n + m; i++) {
int u = -1, minn = inf;
for (int j = 1; j <= n + m; j++) {
if (visit[j] == false && dis[j] < minn) {
u = j;
minn = dis[j];
}
}
if (u == -1) break;
visit[u] = true;
for (int v = 1; v <= n + m; v++) {
if (visit[v] == false && dis[v] > dis[u] + e[u][v])
dis[v] = dis[u] + e[u][v];
}
}
for (int i = 1; i <= n; i++) {
if (dis[i] > ds) {
mindis = -1;
break;
}
if (dis[i] < mindis) mindis = dis[i];
aver += 1.0 * dis[i];
}
if (mindis == -1) continue;
aver = aver / n;
if (mindis > ansdis) {
ansid = index;
ansdis = mindis;
ansaver = aver;
}
else if (mindis == ansdis && aver < ansaver) {
ansid = index;
ansaver = aver;
}
}
if (ansid == -1)
printf("No Solution");
else
printf("G%d\n%.1f %.1f", ansid - n, ansdis, ansaver);
return 0;
}
再翻我一次牌吧,小姐姐~mua!
目前java版好像只有乙级。。。
不知道我可不可pull request呢
当使用全局数组时可以通过测试点二,如下图。
但是当使用局部数组并使用 fill() 置零后测试点二不通过,如下图
除了声明数组以外的代码都相同,代码如下,但是结果不一样....求解....
int main(){
int cnum,mnum;
scanf("%d %d",&cnum,&mnum);
int table[1005];
fill(table, table + 1005, 0);
for(int i = 0; i < cnum; i++){
int temp;
scanf("%d",&temp);
table[temp]++;
}
for(int i = 0; i < 1005; i++){
if(table[i] && table[mnum - i]){
if((i == mnum - i) && table[i] <= 1){
continue;
}else{
printf("%d %d\n",i,mnum - i);
return 0;
}
}
}
printf("No Solution");
}
乙级第38题的数组 a 没有存在的必要。
用个 int 就行。
直接上代码,使用upper_bound()
#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int main() {
int n;
long long p;
cin >> n >> p;
if (n == 0) {
cout << n;
return 0;
}
long long int *a = new long long int[n];
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
int result = 1;
for (int i = 0; i < n; i++) {
result = max((int)(upper_bound(a, a+n, a[i] * p) - (a+i)), result);
}
cout << result;
return 0;
}
抱歉哈,我的是Win系统,pull request的时候会因为文件名神马的,不太方便。
After all,幸苦你啦
女神级大佬,膜拜
膜拜学姐~
弱鸡来问下B1067那道题,为啥总是拿不到满分,学姐能指教下吗,我的qq2567432944,没拿满分有点别扭感觉
``#include
#include
#include
using namespace std;
const int maxn = 305;
const int N =30010;
struct Node{
char name[15];
int score,local,rankl,rankt;
}E[N];
bool cmp(Node a,Node b){
if(a.score != b.score)
return a.score >b.score;
else return strcmp(a.name,b.name)<0;
}
int main(){
int n,k,num=0;
char id[15];
scanf("%d",&n);
for(int i=1;i <= n;i++){
scanf("%d",&k);
Node stu[maxn]={0};
int j;
for(j=0;j<k;j++){
scanf("%s%d",stu[j].name,&stu[j].score);
}
sort(stu,stu+j,cmp);
strcpy(E[num].name ,stu[0].name);
E[num].score = stu[0].score;
E[num].local = i;
E[num++].rankl = 1;
for(int v=1;v < j;v++){
if(stu[v-1].score==stu[v].score){
stu[v].rankl =stu[v-1].rankl;
}else{
stu[v].rankl= v+1;
}
strcpy(E[num].name ,stu[v].name);
E[num].score = stu[v].score;
E[num].local = i;
E[num].rankl = stu[v].rankl;
num++;
}
}
sort(E,E+num,cmp);
E[0].rankt = 1;
for(int v=1;v < num;v++){
if(E[v-1].score==E[v].score){
E[v].rankt = E[v-1].rankt;
}else{
E[v].rankt= v+1;
}
}
printf("%d\n",num);
for(int v=0;v < num;v++){
printf("%s %d %d %d\n",E[v].name,E[v].rankt,E[v].local,E[v].rankl);
}
return 0;
}
#include <stdio.h>
void printFormat(int n) {
if (n < 0) { // 如果 n 负数
putchar('-'); // 打印负号
printFormat(-n); // 用函数自身格式化打印正数
} else if (n < 1000) { // 如果 n 介于 [0, 1000)
printf("%d", n); // 直接打印
} else { // 如果 n >= 1000
printFormat(n / 1000); // 使用函数本身输出去掉低三位的 n
putchar(','); // 插入逗号
printf("%03d", n % 1000); // 打印低三位
}
}
int main() {
int a, b;
scanf("%d %d", &a, &b);
printFormat(a + b);
return 0;
}
Would mind telling me about this algorithm, I use another algorithm and passed the test. I want to exchange thoughts with you.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.