poj 1328贪心算法,一直WA

根据网上的思路写了下代码,测试了几个用例都没问题,哪个大神帮忙看下哪里有问题啊。。。

题意:假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧,而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上,只能覆盖d距离,所以如果小岛能够被覆盖到的话,它们之间的距离最多为d。

题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目

 #include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
using namespace std;

struct dot
{
    int x;
    int y;
}abc[10000];

float left(dot a,int r)
{
    return a.x - sqrt(r*r*1.0 - a.y*a.y*1.0);
}

float right(dot a, int r)
{
    return a.x + sqrt(r*r*1.0 - a.y*a.y*1.0);
}

int comp(const void* a, const void* b)
{
    int aa = (*(dot*)a).x;
    int bb = (*(dot*)b).x;
    return aa - bb;
}


int main()
{
    int num, r;
    cin >> num >> r;
    bool flag = false;
    int count = 0;
    int ans[1000];
    memset(ans, 0, sizeof(ans));
    while (num != 0 && r != 0)
    {
        count++;
        int cir = 0;
        for (int i = 0; i < num; i++)
        {
            dot temp;
            cin >> temp.x >> temp.y;
            if (temp.y > r||temp.y<0)
                flag = true;
            abc[i] = temp;
        }
        if (flag)
        {
            ans[count] = -1;
            cout << "Case " << count << ": " << -1 << endl;
        }
        else
        {
            qsort(abc, num, sizeof(abc[0]), comp);
            dot temp = abc[0];
            cir++;
            float now = right(temp, r);
            for (int i = 1; i < num; i++)
            {
                temp = abc[i];
                if (now >= left(temp, r))
                    continue;
                else
                {
                    now = right(temp, r);
                    cir++;
                }
            }
            ans[count] = cir;
            cout << "Case " << count << ": " << cir << endl;
        }

        cin >> num >> r;
    }

    return 0;

}

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
poj1328求大神 题意如下
Input The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases. The input is terminated by a line containing pair of zeros Output For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case. Sample Input 3 2 1 2 -3 1 2 1 1 2 0 2 0 0 Sample Output Case 1: 2 Case 2: 1 题意:假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧,而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上,只能覆盖d距离,所以如果小岛能够被覆盖到的话,它们之间的距离最多为d。 题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。 ``` #include <algorithm> #include <vector> #include <limits> #include <string> using namespace std; double d; int n; int t=0; bool flag = false; vector <int> ans; struct data { public: double start; double ends; }; bool compare(data a,data b) { return a.ends<b.ends; } int main() { while(cin>>n>>d&&(n!=0&&d!=0)) { vector <data> ils (n); int x,y,i; i=0; while(i!=n&&cin>>x>>y) { if(y>d) { flag = true; } data item; item.start = x - sqrt(d*d-y*y); item.ends = x + sqrt(d*d-y*y); ils[i] = item; ++i; } sort(ils.begin(),ils.end(),compare); i=0; int num = 0; double range; while(i<n) { range = ils[i].ends; while(++i<n) { if(ils[i].start>range) break; } ++num; } if(flag) { ans.push_back(-1); } else { ans.push_back(num); } n=d=i=num=0; ils.clear(); flag = false; } for(t=0;t!=ans.size();t++) { cout<<"case "<<t+1<<": "<<ans[t]<<endl; } return 0; } ```
poj 1328 Running time 错误 求助
#include<iostream> using namespace std; #include<math.h> void sort_com(int dot[][2],int num)//对小岛根据x坐标排序 { int judge=1; while(judge) { judge=0; for(int i=0;i<num-1;i++) { if(dot[i][0]>dot[i+1][0]) { int temp1=dot[i][0]; int temp2=dot[i][1]; dot[i][0]=dot[i+1][0]; dot[i][1]=dot[i+1][1]; dot[i+1][0]=temp1; dot[i+1][1]=temp2; judge=1; } } } } float range(int y,int d) //求一个岛在海岸线上所允许的圆心值范围,-1表示不存在 { if(d*d-y*y<0) return -1; return sqrt((float)(d*d-y*y)); } int select_dot(int dot[][2],int d,int num)//寻找区间最少数 { int b[100][2]; for(int i=0;i<num;i++) { float delt=range(dot[i][1],d); if(delt<0) return -1; b[i][0]=dot[i][0]-delt; b[i][1]=dot[i][0]+delt; } int center=b[0][1]; int result=1; for(int i=0;i<num;i++) { if(b[i][0]>center) { center=b[i][1]; result++;//需要增加一个雷达 } } return result; } int main(void) { int dot[100][2],d,num,times=0;//times表示有几个case int answer[100]; for(int i=0;i<100;i++)//初始化 for(int j=0;j<2;j++) dot[i][j]=0; cin>>num>>d; while(d!=0||num!=0) { for(int i=0;i<num;i++) cin>>dot[i][0]>>dot[i][1]; sort_com(dot,num); answer[times]=select_dot(dot,d,num); times++; cin>>num>>d; } for(int i=1;i<=times;i++) cout<<"Case "<<i<<": "<<answer[i-1]<<endl;//输出 return 0; } poj 显示Running time 的错误过不了,求助
ACM北大POJ_1376代码提交一直WA,求大神看看哪里错了?呜呜
---------- #include <iostream> #include <cstring> #include <queue> using namespace std; bool Map[55][55]; bool vis[55][55][4]; //[4] 四个directions,坐标和方向都相同时不能同时经过该点两次; int M,N; bool flag=false; //找到路径置为true; typedef struct { int x,y; //坐标; int time; //走到当前格子所用时间; int dir; //当前格子所朝方向; }point; point Start,End; bool canPass(int x,int y,int direction) { if(x<=0||x>=M||y<=0||y>=N) //走到边界; return false; if(vis[x][y][direction]|| !Map[x][y]|| !Map[x+1][y]|| !Map[x][y+1]||!Map[x+1][y+1]) return false; else return true; } void bfs() { point temp,temp1; queue <point> q; while(!q.empty()) //调用完后要清空队列; q.pop(); int dir1,dir2; q.push(Start); vis[Start.x][Start.y][Start.dir]=true; while(!q.empty()) { temp=q.front(); q.pop(); if((temp.x==End.x)&&(temp.y==End.y)) //到达终点; { flag=true; cout<<temp.time<<endl; return; } dir1=(temp.dir+1)%4; //0为south,1为east,2为north,3为west,每次转90度刚好dir+1或dir-1对4取余即可 dir2=(temp.dir-1+4)%4; temp1=temp; if(!vis[temp1.x][temp1.y][dir1]) //相同点不同方向没有访问过则入队; { vis[temp1.x][temp1.y][dir1]=true; temp1.dir=dir1; temp1.time++; q.push(temp1); } temp1=temp; if(!vis[temp1.x][temp1.y][dir2]) { vis[temp1.x][temp1.y][dir2]=true; temp1.dir=dir2; temp1.time++; q.push(temp1); } for(int i=0;i<3;i++) //走一步,两步,三步的情况全部进栈; { switch(temp.dir) { case 0: temp.x++; break; case 1: temp.y++; break; case 2: temp.x--; break; case 3: temp.y--; break; } if(!canPass(temp.x,temp.y,temp.dir)) break; else { vis[temp.x][temp.y][temp.dir]=true; if(i==0) temp.time++; //走1,2,3步都只需要耗时1秒,只需要第一次走一步时间加1就行; q.push(temp); } } } } int main() { int t; string s; while(cin>>M>>N&&(M||N)) { memset(Map,false,sizeof(Map)); memset(vis,false,sizeof(vis)); flag=false; for(int i=1;i<=M;i++) { for(int j=1;j<=N;j++) { cin>>t; Map[i][j]=t==0?true:false; //true(0)表示可以通行,false(1)表示不能走; } } cin>>Start.x>>Start.y>>End.x>>End.y; cin>>s; if(!canPass(Start.x,Start.y,Start.dir) ||!canPass(End.x,End.y,End.dir)) { cout<<"-1"<<endl; continue; //起始点和终点如果在边界或本身是障碍物则直接输出-1返回; } if(s=="south") Start.dir=0; else if(s=="east") Start.dir=1; else if(s=="north") Start.dir=2; else if(s=="west") Start.dir=3; bfs(); if(flag==false) cout<<"-1"<<endl; } return 0; }
poj 2058算法题Word Encoding完整代码
题目描述 In any language, certain combinations of letters do not appear (or at least appear so seldom that they can be considered non-existent). For instance, there are no English words containing the three letter combination buv as a substring. Given a list of letter combinations that do not exist, the number of possible "words" in a language can be reduced a lot (a "word" here means any combination of letters that doesn't contain any of the given letter combinations as a substring). If we order all such words by increasing length, ordering words of the same length alphabetically, we can enumerate them starting from 1. Assume that the alphabet always consists of the lower case letters 'a' to 'z'. For instance, if the list only contains the combinations q, ab and aaa, the words would be enumerated like this: 1. a 2. b ... 16. p 17. r ... 26. aa 27. ac ... 649. zz 650. aac Given the list of letter combinations, write a program that for a given word outputs its number, and for a given number ouputs its word. You can assume that none of the words will exceed 20 characters and no number will be greater than 2 000 000 000 (for both input and output). 输入 The input will contain several test cases. The number of test cases T appears on a line by itself. Then follow T test cases. Each test case starts with a line containing two integers,N (the number of letter combinations, non-negative, at most 1 000) and M (the number of queries for this list, positive, at most 100). Then follow N lines, each containing a lower case letter combination (between 1 and 3 letters, inclusive). After that follow M lines, each containing either a positive integer or a lower case word. If it's a word, it will not contain any of the combinations of letters in the list for this test case. If it's a number, it will not be greater than the number of words in the language. 输出 For each query, output a single line containing either the word's corresponding number, or the number's corresponding word. 样例输入 2 3 4 q ab aaa 16 r 27 aac 7 2 a b c d ef ghi ijk 102345678 ksvfuw 样例输出 p 17 ac 650 xexgun 39174383
Catch the cow(POJ3278) 编译器上没问题, OJ上一直runtime error?
[原题网址](http://poj.org/problem?id=3278 "Catch the cow") 下面是我已经在编译器上通过的代码,但是OJ上始终会RE (使用的是广度优先搜索的方法) ``` #include <stdio.h> #include <stdlib.h> #define MAX_N 100000 int n, k, ans; int que[MAX_N+10][2]; int vis[MAX_N+10]; int head, tail; void bfs( int x); void enqueue ( int x, int time); int main(void) { scanf("%d %d", &n, &k); if( n>k) { ans = n-k; } else { bfs(n); } printf("%d\n", ans); return 0; } void bfs( int x) { enqueue(x, 0); vis[x] = 1; while(head<tail) { int i, nowx, nowtime; nowx = que[head][0]; nowtime = que[head][1]; head ++; if( nowx == k) { ans = nowtime; break; } for( i=1; i<=3; i++) { if( i==1 && vis[nowx-1]!=1 && nowx-1>=0 && nowx-1 <= MAX_N) { enqueue( nowx-1, nowtime+1); vis[nowx-1] = 1; } if( i==2 && vis[nowx+1]!=1 && nowx+1>=0 && nowx+1 <= MAX_N) { enqueue( nowx+1, nowtime+1); vis[nowx+1] = 1; } if( i==3 && vis[nowx*2]!=1 && nowx*2>=0 && nowx*2 <= MAX_N) { enqueue( nowx*2, nowtime+1); vis[nowx*2] = 1; } } } } void enqueue( int x, int time) { que[tail][0] = x; que[tail][1] = time; tail ++; } ``` 一开始查了之后说可能是什么栈空间不够,就尝试了一下动态分配空间 (萌新还没学指针,就在网上照猫画虎贴了进去), 但是数字只要大一点程序就无法输出结果 更改后的代码如下: ``` #include <stdio.h> #include <stdlib.h> #define MAX_N 100001 int n, k, ans; //int que[MAX_N+10][2]; /*之前的方案,但同样RE了,可能是空间不足(?),所以尝试如下动态分配的方法*/ //int vis[MAX_N+10]; int head, tail; void bfs( int x, int **que, int *vis); void enqueue ( int x, int time, int **que); int main(void) { int **que; int i, j; int *vis; que = (int**)malloc(sizeof(int*)*MAX_N); //为两个数组分配空间 for( i=0; i<MAX_N; i++) { que[i] = (int*)malloc(sizeof(int)*2); } vis = (int*)malloc(sizeof(int)*MAX_N); scanf("%d %d", &n, &k); if( n>k) { ans = n-k; } else { bfs(n, que, vis); //进入深搜 } printf("%d\n", ans); return 0; } void bfs( int x, int **que, int *vis) { enqueue(x, 0, que); vis[x] = 1; while(head<tail) { int i, nowx, nowtime; nowx = que[head][0]; //队列数据的取出 nowtime = que[head][1]; head ++; if( nowx == k) //结束条件 { ans = nowtime; break; } for( i=1; i<=3; i++) //对三种可能进行遍历 { if( i==1 && vis[nowx-1]!=1 && nowx-1>=0 && nowx-1 <= MAX_N) { enqueue( nowx-1, nowtime+1, que); vis[nowx-1] = 1; } if( i==2 && vis[nowx+1]!=1 && nowx+1>=0 && nowx+1 <= MAX_N) { enqueue( nowx+1, nowtime+1, que); vis[nowx+1] = 1; } if( i==3 && vis[nowx*2]!=1 && nowx*2>=0 && nowx*2 <= MAX_N) { enqueue( nowx*2, nowtime+1, que); vis[nowx*2] = 1; } } } } void enqueue( int x, int time, int **que) //队列数据的写入 { que[tail][0] = x; que[tail][1] = time; tail ++; } ``` 请教一下大佬们上面RE的原因到底是什么, 还有下面的动态分配有什么问题,感激不尽
关于POJ 2503 ELFhash WA的问题
先附上我的代码: ``` #include"iostream" #include"cstring" #include"cstdlib" #include"cstdio" #define N 100003 using namespace std; typedef struct node { char english[15]; char foreign[15]; struct node* next; }point; point data[N]; int elfhash(char* str) { unsigned long hash=0; unsigned long x=0; while(*str) { hash=(hash<<4)+(*str++); if((x=hash&0xF0000000L)!=0) { hash^=(x>>24); } hash&=~x; } return hash%N; } int main() { char ppp[30]; char s1[12]; char s2[12]; memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); while(gets(ppp) && ppp[0]!='\0') { sscanf(ppp,"%s %s",s1,s2); int key=elfhash(s2); point* k=new point; memset(k,0,sizeof(k)); //这里采用头插法 strcpy(k->english,s1); strcpy(k->foreign,s2); k->next=data[key].next; data[key].next=k; memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); } while(gets(ppp)) { int key=elfhash(ppp); point* k=data[key].next; if(k==NULL) printf("eh\n"); else { while(k!=NULL) { if(strcmp(k->foreign,ppp)==0) { //while(1); printf("%s\n",k->english); //找到匹配的我退出 break; } k=k->next; } } memset(ppp,0,sizeof(ppp)); } return 0; } ``` 本题我才用了ELFhash的方法,但是一直在WA,所以很是无语,找不出BUG,在这里悬赏,大恩不言谢
为什么POJ中有很多题目,用G++就WA,用C++就是AC的
为什么POJ中有很多题目,用G++就WA,用C++就是AC的
poj1465 WA 较怪 求解
与同学对拍过,但一交就错 #include <iostream> #include <cmath> #include <cstring> #include <cstdio> #include <string> #include <cstdlib> using namespace std; struct f1 { int d[101],s,t; }f[10000],a; int i,j,k,n,m,b[15],r; bool fl[5050],flag; void cale(int i) { int r=a.t; if(a.d[r]>999) {a.t++;a.d[r+1]=a.d[r]/1000;} for(j=r;j>=1;j--) { a.d[j]=(a.d[j]*10+a.d[j-1]/1000)%10000; } a.d[1]+=i; } void bfs() { int l=1,i; while(l<=r) { for(i=1;i<=m;i++) { a=f[l]; a.s=(a.s*(10%n)%n+b[i]%n)%n; if(!fl[a.s]) { fl[a.s]=true; cale(b[i]); r++; f[r]=a; } if(a.s==0) { cout<<a.d[a.t]; for(int u=a.t-1;u>=1;u--) { k=999; while(a.d[u]<k) { cout<<'0'; k/=10; } printf("%d",a.d[u]); } flag=true; cout<<endl; return; } } l++; } } void qsort(int l,int r) { int i=l,j=r,x=b[(l+r)/2]; while (i<=j) { while (b[i]<x) i++; while (b[j]>x) j--; if (i<=j) { k=b[i];b[i]=b[j];b[j]=k; i++;j--; } } if (i<r) qsort(i,r); if (l<j) qsort(l,j); } int main() { while(scanf("%d%d",&n,&m)==2) { r=0; for(i=1;i<=m;i++) { scanf("%d",&b[i]); if(b[i]==n) {cout<<n<<endl; continue;} } if(n==0) {cout<<n<<endl; continue;} qsort(1,m); flag=false; for(i=1;i<10000;i++) { f[i].s=f[i].t=0; memset(f[i].d,0,sizeof(f[i].d)); } memset(fl,false,sizeof(fl)); for(i=1;i<=m;i++) if(b[i]!=0) {r++;f[r].d[1]=b[i];f[r].s=b[i]%n;f[r].t=1; fl[f[r].s]=true;} bfs(); if(!flag) cout<<0<<endl; } return 0; }
POJ魔兽世界一之备战:运行结果输出正确,但是poj总是WA(wrong answer),大家帮忙找找原因
> 题目链接:http://cxsjsx.openjudge.cn/ewar201901/1/ Dev C++和CLion上能过,输出与题目要求一致,可是poj提示WA,大家帮忙找找原因。 ``` #include <iostream> #include <string> #include <string.h> using namespace std; const int WARRIOR_NUM = 5; const int SPACE_NUM = 10; class Headquarter{ public: int total_hp; int color; string colorName[SPACE_NUM]; string names[SPACE_NUM]; int warrior_num[SPACE_NUM]; int produce_seq[SPACE_NUM]; int hp[SPACE_NUM]; public: void Init(int, int, const int *, const int*); int Produce(int); }; void Headquarter::Init(int color_, int thp, const int * ini_hp, const int* seq) { color = color_; total_hp = thp; memcpy(hp, ini_hp, SPACE_NUM * sizeof(int)); memcpy(produce_seq, seq, SPACE_NUM * sizeof(int)); for(int i=0;i<WARRIOR_NUM;i++) warrior_num[i]=0; colorName[0] = "red",colorName[1] = "blue"; names[0] = "dragon",names[1] = "ninja",names[2] = "iceman",names[3] = "lion",names[4] = "wolf"; } int Headquarter::Produce(int t) { int no = t % WARRIOR_NUM; int warrior_id = produce_seq[no]; if(total_hp - hp[warrior_id] >= 0) { total_hp -= hp[warrior_id]; warrior_num[warrior_id]++; printf("%03d %s %s %d born with strength %d,%d %s in %s headquarter\n", t,colorName[color].c_str(),names[warrior_id].c_str(),t+1,hp[warrior_id], warrior_num[warrior_id],names[warrior_id].c_str(),colorName[color].c_str()); return 1; } else { no++; while(no != t % WARRIOR_NUM) { int new_id = produce_seq[no]; if(total_hp - hp[new_id] >= 0) { total_hp -= hp[new_id]; warrior_num[new_id]++; printf("%03d %s %s %d born with strength %d,%d %s in %s headquarter\n", t,colorName[color].c_str(),names[new_id].c_str(),t+1,hp[new_id], warrior_num[new_id],names[new_id].c_str(),colorName[color].c_str()); return 1; } else{no = (no+1)%WARRIOR_NUM;} } printf("%03d %s headquarter stops making warriors\n",t,colorName[color].c_str()); return 0; } } int main() { int test_num; int ini_hp[SPACE_NUM]; int tNum = 1; Headquarter RedHead, BlueHead; int redSeq[SPACE_NUM] = {2, 3, 4, 1, 0}; int blueSeq[SPACE_NUM] = {3, 0, 1, 2, 4}; cin>>test_num; while(tNum<=test_num) { int t = 0; int stop_sign = 1; printf("Case:%d\n", tNum); int thp; cin>>thp; for( int i = 0;i < WARRIOR_NUM;i++) cin>>ini_hp[i]; RedHead.Init(0,thp,ini_hp,redSeq); BlueHead.Init(1,thp,ini_hp,blueSeq); int s1=1,s2=1; while(stop_sign) { if(s1) s1 = RedHead.Produce(t); if(s2) s2 = BlueHead.Produce(t); t++; if(s1==0 && s2==0) stop_sign = 0; } tNum++; } return 0; } ```
POJ 1028 一直Wrong answer....求助
题目在http://poj.org/problem?id=1028 我的代码如下: #include <iostream> #include <string> #include <vector> using namespace std; int main() { unsigned current; string userCommand; vector<string> webs; webs.push_back("http://www.acm.org/"); while(getline(cin, userCommand)) { if(userCommand.find("VISIT ") == 0) { webs.push_back(userCommand.substr(6)); current = webs.size() - 1; cout << webs[current] << endl; } else if(userCommand == "BACK") { if(current == 0) cout << "Ignored" << endl; else cout << webs[--current] << endl; } else if(userCommand == "FORWARD") { if(current == webs.size() - 1) cout << "Ignored" << endl; else cout << webs[++current] << endl; } else if(userCommand == "QUIT") break; } return 0; } 求大神们帮我看看好不。。。。非常感谢
关于floyed算法实现的问题
我想请问一下,今天在刷poj3259的时候 用floyed来做,发现对floyed的实现又出现了问题 我想请问一下我们给邻接矩阵中不相邻,的点附上正无穷大 的时候(0x3fffffff)那么我在进行松弛的时候 for(k:1-n) for(i:1-n) for(j:1-n) { if(map[i][k]||map[k][j])这一句该不该加上 } 按照算法本质看加上对,但是poj3259加上就WA,有些怀疑自己对floyed的理解了,请大神解答
POJ 1011 Sticks (dfs) 我照着题解敲的,哪位大佬看看为什么WA了
[code=c]#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int v[70]; int a[70]; int n; int ans; int dfs(int index, int sum)//下标和当前木棒长度的总和 { sum += a[index]; int l=sum; if (sum == ans)return l;//找到就返回 if (sum > ans)return l;//大了就说明选择的这根木棒不对 返回 for (int i = index + 1; i < n; i++)//将所以可以选择的木棒枚举一遍 { if (v[i] == 0) { v[i] = 1; l=dfs(i, sum); if (l>ans)//大了就找下一个 { v[i] = 0; while (1)//去除与这个长度相等的木棒 因为肯定也不满足 { if (a[i + 1] != a[i])break; i++; } } else if (l < ans) { return l; }//如果长度不够 就直接结束dfs 因为后面的木棒长度更小 永远也得不到结果 else return l;//找到了 就退出dfs } } return l; //枚举完了长度还不够 退出dfs } bool cmp(int a, int b) { return a > b; } int main() { while (cin >> n) { if (n == 0)break; int k=0; for (int i = 0; i < n; i++) { cin >> a[i]; k+=a[i]; //所有的和 作为结束的条件 } sort(a, a + n, cmp);//从大到小排序 for (ans = a[0];ans<k; ans++)//结果一定不小于最长的木棒 { bool flag = true;//判断是否找到循环退出的条件 memset(v, 0, sizeof(v));//每次没找到都要置零 for (int j = 0; j < n; j++)//把每个木棒遍历一遍是否能找到答案 { if (v[j] == 0) { v[j] = 1; if (dfs(j, 0) != ans) { flag = false; break; }//如果不对就退出这个循环 看下一个结果是否正常 } } if (flag == true)break; } cout << ans << endl; } return 0; }[/code]
poj1251求助,测试数据通过但wrong answer
用的Kruskal算法,没用并查集而是在结构体里多了一个变量判断是否是一个连通量。 结果wrong answer。 #include<cstdio> #include<algorithm> using namespace std; struct in{ int f,n,price; }; int main() { int m=1,are[10000],root=1,i; while(m!=0) { int total=0,head=1,tail=1,q[1000]={0},mark=1; in r[2000]; int j,k,z,h,g,x,flag=1,s; char c,d; total=0; scanf("%d",&m); if(m==0) break; for(i=1;i<=m-1;i++) { scanf("\n%c",&c); z=c-'A'+1; scanf("%d",&g); for(j=1;j<=g;j++) { scanf("\n%c%d",&d,&k); h=d-'A'+1; r[flag].price=k; r[flag].f=z; r[flag].n=h; flag++; } } flag--; for(i=1;i<=flag;i++) //排序; for(j=1;j<=flag-i;j++) { if(r[j].price>r[j+1].price) { r[j].price=r[j].price+r[j+1].price; r[j+1].price=r[j].price-r[j+1].price; r[j].price=r[j].price-r[j+1].price; r[j].f=r[j].f+r[j+1].f; r[j+1].f=r[j].f-r[j+1].f; r[j].f=r[j].f-r[j+1].f; r[j].n=r[j].n+r[j+1].n; r[j+1].n=r[j].n-r[j+1].n; r[j].n=r[j].n-r[j+1].n; } } for(i=1;i<=flag;i++) { //判断是否是一个连通分量 if(q[r[i].n]==0&&q[r[i].f]==0) { total=total+r[i].price; q[r[i].n]=mark; q[r[i].f]=mark; mark++; continue; } if(q[r[i].n]!=q[r[i].f]) { total=total+r[i].price; if(q[r[i].n]==0) { q[r[i].n]=q[r[i].f]; } else if(q[r[i].f]==0) { q[r[i].f]=q[r[i].n]; } else if(q[r[i].n]!=0&&q[r[i].f]!=0) { for(j=1;j<=26;j++) { if(q[j]==q[r[i].f]) q[j]=q[r[i].n]; } } } } are[root]=total; root++; } root--; for(i=1;i<=root;i++) { printf("%d",are[i]); if(i<root) printf("\n"); } }
poj2488 样例过了为什么还是WA???有人帮忙看一下吗?
```.c poj2488 样例过了为什么还是WA??? ``` 有人帮忙看一下吗? ```.c #include <stdio.h> #include <stdlib.h> #define max 30 struct pos { int x; int y; int flag; }map[max][max],res[max]; int n,m,num,cnt=1; int l=1; int dx[9]={-2,-2,-1,-1,1,1,2,2}; int dy[9]={-1,1,-2,2,-2,2,-1,1}; void dfs(int x, int y) { if(l==0) return; int i,nx,ny,flag=0; for(i=0; i<9; i++) { nx=x+dx[i]; ny=y+dy[i]; if(nx<=n && nx>=1 && ny<=m && ny>=1 && map[nx][ny].flag==1 )//&&(dy[i]==1||dy[i]==-2))//保证字典序 { flag=1; cnt++; map[nx][ny].flag=0; res[cnt].x=nx; res[cnt].y=ny; dfs(nx,ny); cnt--; map[nx][ny].flag=1; } } //if(flag==0)//无路可走 //{ if(cnt==n*m) { l=0; printf("Scenario #%d:\n",3-num); for(i=1; i<=n*m; i++) { printf("%c%d",'A'+res[i].y-1,res[i].x); } printf("\n"); if(num!=0) printf("\n"); } return; //} } int main() { int i,j; scanf("%d",&num); while(num--) { scanf("%d %d",&n,&m); l=1; res[cnt].x=1,res[cnt].y=1; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { map[i][j].flag=1; //map[i][j].x=i; } } map[1][1].flag=0; dfs(1,1); if(l==1)//impossible { printf("Scenario #%d:\n",3-num); printf("impossible\n"); if(num!=0) printf("\n"); } } return 0; } ```
poj2159求助 关于字符串的输入问题
题目链接:http://poj.org/problem?id=2159 我的代码 ``` #include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <string> using namespace std; int num1[27], num2[27]; char a[105], b[105]; int main() { int lena, lenb, j = 0, k = 0, dai = 0, count = 0; //fgets(a, 100, stdin); //fgets(b, 100, stdin); scanf("%s%s",a,b); if (lena != lenb) { cout << "NO" << endl; return 0; } for (int i = 0; i < strlen(a); i++) { num1[a[i] - 'A']++; num2[b[i] - 'A']++; } sort(num1, num1 + 26); sort(num2, num2 + 26); for (int i = 0; i < 26; i++) { if (num1[i] != num2[i]) { printf("NO\n"); return 0; } } printf("YES\n"); return 0; } ``` 这个是可以AC的!但是如果把字符串a,b的读取方式换成被注释掉的fgets那种,就会wrong answer 请教一下这是为什么,难道以后没有空格回车的输入都要尽量用scanf来弄吗,我以前都是fgets没有出过问题
初学搜索 求助 POJ 3309 思路...
RT 链接: [点击打开](http://poj.org/problem?id=3309 "")
poj 1226我的代码为什么wa,求hack,给出测试数据,或者思路的错误
代码如下: //#include<bits\stdc++.h> #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> using namespace std; const int maxn = 105; int next[maxn]; int ans[maxn]; string s[maxn]; void getnext(string a) { int i = 0;int j = -1; next[0] = -1; while(i<a.length()){ if(j == -1||a[i] == a[j]) { i++;j++; next[i] = j; } else j = next[j]; } } int kmp(string a,string b){ getnext(a); int ans = 0; int al = a.size(); int bl = b.size(); //cout<<b<<endl; int i = 0;int j = 0; while(i<bl){ if(j == -1||a[j] == b[i]){ //cout<<i<<" "<<j<<a[j]<<b[i]<<endl; i++;j++; } else{ j = next[j]; } ans = max(ans,j); if(j == al) j = next[j]; } return ans; } string jianyi(string a){ string b = a; reverse(b.begin(),b.end()); b = b.substr(0,b.size()-1); reverse(b.begin(),b.end()); return b; } int main() { int T; cin>>T; while(T--){ memset(ans,0x3f,sizeof(ans)); int n; cin>>n; if(n == 0) {cout<<"0"<<endl;continue;} if(n == 1){ cin>>s[0]; cout<<s[0].size()<<endl; continue; } int mini = 0; int minsize = 0x3f3f3f; for(int i = 0;i<n;i++){ cin>>s[i]; if(s[i].size()<minsize) { minsize = s[i].size(); mini = i; } } string a = s[mini]; string b = a; reverse(b.begin(),b.end()); for(int i = 0;i<s[mini].length();i++){ for(int j = 0;j<n;j++){ if(j == mini)continue; // cout<<i<<" "<<kmp(a,s[j])<<" "<<kmp(b,s[j])<<endl; ans[i] = min(ans[i],max(kmp(a,s[j]),kmp(b,s[j]))); } // cout<<ans[i]<<endl; a = jianyi(a); b = jianyi(b); } int ant = 0; for(int i = 0;i<s[mini].length();i++){ //cout<<ans[i]; ant = max(ant,ans[i]); } cout<<ant<<endl; } return 0; }
ACM一道题 poj3523 UVA1601双向广度优先BFS
我没有用双广,用的是紫书上说的把空格提出来重新建了一张图,调试了两天,实在找不出bug,第二组测试数据总是38而不是36。。。 哪位大神做过了这道题,跪求帮助啊!! 链接:http://poj.org/problem?id=3523
poj 1363 线上指导+源代码
poj 1363 线上指导+源代码,最好有注释,并详细跟我解释~
相见恨晚的超实用网站
搞学习 知乎:www.zhihu.com 简答题:http://www.jiandati.com/ 网易公开课:https://open.163.com/ted/ 网易云课堂:https://study.163.com/ 中国大学MOOC:www.icourse163.org 网易云课堂:study.163.com 哔哩哔哩弹幕网:www.bilibili.com 我要自学网:www.51zxw
花了20分钟,给女朋友们写了一个web版群聊程序
参考博客 [1]https://www.byteslounge.com/tutorials/java-ee-html5-websocket-example
爬虫福利二 之 妹子图网MM批量下载
爬虫福利一:27报网MM批量下载    点击 看了本文,相信大家对爬虫一定会产生强烈的兴趣,激励自己去学习爬虫,在这里提前祝:大家学有所成! 目标网站:妹子图网 环境:Python3.x 相关第三方模块:requests、beautifulsoup4 Re:各位在测试时只需要将代码里的变量 path 指定为你当前系统要保存的路径,使用 python xxx.py 或IDE运行即可。
字节跳动视频编解码面经
引言 本文主要是记录一下面试字节跳动的经历。 三四月份投了字节跳动的实习(图形图像岗位),然后hr打电话过来问了一下会不会opengl,c++,shador,当时只会一点c++,其他两个都不会,也就直接被拒了。 七月初内推了字节跳动的提前批,因为内推没有具体的岗位,hr又打电话问要不要考虑一下图形图像岗,我说实习投过这个岗位不合适,不会opengl和shador,然后hr就说秋招更看重基础。我当时
Java学习的正确打开方式
在博主认为,对于入门级学习java的最佳学习方法莫过于视频+博客+书籍+总结,前三者博主将淋漓尽致地挥毫于这篇博客文章中,至于总结在于个人,实际上越到后面你会发现学习的最好方式就是阅读参考官方文档其次就是国内的书籍,博客次之,这又是一个层次了,这里暂时不提后面再谈。博主将为各位入门java保驾护航,各位只管冲鸭!!!上天是公平的,只要不辜负时间,时间自然不会辜负你。 何谓学习?博主所理解的学习,它
程序员必须掌握的核心算法有哪些?
由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,我稍微总结一下我学过的算法知识点,以及我觉得值得学习的算法。这些算法与数据结构的学习大多数是零散的,并没有一本把他们全部覆盖的书籍。下面是我觉得值得学习的一些算法以及数据结构,当然,我也会整理一些看过
大学四年自学走来,这些私藏的实用工具/学习网站我贡献出来了
大学四年,看课本是不可能一直看课本的了,对于学习,特别是自学,善于搜索网上的一些资源来辅助,还是非常有必要的,下面我就把这几年私藏的各种资源,网站贡献出来给你们。主要有:电子书搜索、实用工具、在线视频学习网站、非视频学习网站、软件下载、面试/求职必备网站。 注意:文中提到的所有资源,文末我都给你整理好了,你们只管拿去,如果觉得不错,转发、分享就是最大的支持了。 一、电子书搜索 对于大部分程序员...
linux系列之常用运维命令整理笔录
本博客记录工作中需要的linux运维命令,大学时候开始接触linux,会一些基本操作,可是都没有整理起来,加上是做开发,不做运维,有些命令忘记了,所以现在整理成博客,当然vi,文件操作等就不介绍了,慢慢积累一些其它拓展的命令,博客不定时更新 顺便拉下票,我在参加csdn博客之星竞选,欢迎投票支持,每个QQ或者微信每天都可以投5票,扫二维码即可,http://m234140.nofollow.ax.
比特币原理详解
一、什么是比特币 比特币是一种电子货币,是一种基于密码学的货币,在2008年11月1日由中本聪发表比特币白皮书,文中提出了一种去中心化的电子记账系统,我们平时的电子现金是银行来记账,因为银行的背后是国家信用。去中心化电子记账系统是参与者共同记账。比特币可以防止主权危机、信用风险。其好处不多做赘述,这一层面介绍的文章很多,本文主要从更深层的技术原理角度进行介绍。 二、问题引入 假设现有4个人...
Python 基础(一):入门必备知识
目录1 标识符2 关键字3 引号4 编码5 输入输出6 缩进7 多行8 注释9 数据类型10 运算符10.1 常用运算符10.2 运算符优先级 1 标识符 标识符是编程时使用的名字,用于给变量、函数、语句块等命名,Python 中标识符由字母、数字、下划线组成,不能以数字开头,区分大小写。 以下划线开头的标识符有特殊含义,单下划线开头的标识符,如:_xxx ,表示不能直接访问的类属性,需通过类提供
这30个CSS选择器,你必须熟记(上)
关注前端达人,与你共同进步CSS的魅力就是让我们前端工程师像设计师一样进行网页的设计,我们能轻而易举的改变颜色、布局、制作出漂亮的影音效果等等,我们只需要改几行代码,不需...
国产开源API网关项目进入Apache孵化器:APISIX
点击蓝色“程序猿DD”关注我回复“资源”获取独家整理的学习资料!近日,又有一个开源项目加入了这个Java开源界大名鼎鼎的Apache基金会,开始进行孵化器。项目名称:AP...
程序员接私活怎样防止做完了不给钱?
首先跟大家说明一点,我们做 IT 类的外包开发,是非标品开发,所以很有可能在开发过程中会有这样那样的需求修改,而这种需求修改很容易造成扯皮,进而影响到费用支付,甚至出现做完了项目收不到钱的情况。 那么,怎么保证自己的薪酬安全呢? 我们在开工前,一定要做好一些证据方面的准备(也就是“讨薪”的理论依据),这其中最重要的就是需求文档和验收标准。一定要让需求方提供这两个文档资料作为开发的基础。之后开发
网页实现一个简单的音乐播放器(大佬别看。(⊙﹏⊙))
今天闲着无事,就想写点东西。然后听了下歌,就打算写个播放器。 于是乎用h5 audio的加上js简单的播放器完工了。 欢迎 改进 留言。 演示地点跳到演示地点 html代码如下`&lt;!DOCTYPE html&gt; &lt;html&gt; &lt;head&gt; &lt;title&gt;music&lt;/title&gt; &lt;meta charset="utf-8"&gt
Python十大装B语法
Python 是一种代表简单思想的语言,其语法相对简单,很容易上手。不过,如果就此小视 Python 语法的精妙和深邃,那就大错特错了。本文精心筛选了最能展现 Python 语法之精妙的十个知识点,并附上详细的实例代码。如能在实战中融会贯通、灵活使用,必将使代码更为精炼、高效,同时也会极大提升代码B格,使之看上去更老练,读起来更优雅。 1. for - else 什么?不是 if 和 else 才
数据库优化 - SQL优化
前面一篇文章从实例的角度进行数据库优化,通过配置一些参数让数据库性能达到最优。但是一些“不好”的SQL也会导致数据库查询变慢,影响业务流程。本文从SQL角度进行数据库优化,提升SQL运行效率。 判断问题SQL 判断SQL是否有问题时可以通过两个表象进行判断: 系统级别表象 CPU消耗严重 IO等待严重 页面响应时间过长
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
通俗易懂地给女朋友讲:线程池的内部原理
餐厅的约会 餐盘在灯光的照耀下格外晶莹洁白,女朋友拿起红酒杯轻轻地抿了一小口,对我说:“经常听你说线程池,到底线程池到底是个什么原理?”我楞了一下,心里想女朋友今天是怎么了,怎么突然问出这么专业的问题,但做为一个专业人士在女朋友面前也不能露怯啊,想了一下便说:“我先给你讲讲我前同事老王的故事吧!” 大龄程序员老王 老王是一个已经北漂十多年的程序员,岁数大了,加班加不动了,升迁也无望,于是拿着手里
经典算法(5)杨辉三角
杨辉三角 是经典算法,这篇博客对它的算法思想进行了讲解,并有完整的代码实现。
编写Spring MVC控制器的14个技巧
本期目录 1.使用@Controller构造型 2.实现控制器接口 3.扩展AbstractController类 4.为处理程序方法指定URL映射 5.为处理程序方法指定HTTP请求方法 6.将请求参数映射到处理程序方法 7.返回模型和视图 8.将对象放入模型 9.处理程序方法中的重定向 10.处理表格提交和表格验证 11.处理文件上传 12.在控制器中自动装配业务类 ...
腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?
昨天,有网友私信我,说去阿里面试,彻底的被打击到了。问了为什么网上大量使用ThreadLocal的源码都会加上private static?他被难住了,因为他从来都没有考虑过这个问题。无独有偶,今天笔者又发现有网友吐槽了一道腾讯的面试题,我们一起来看看。 腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹? 在互联网职场论坛,一名程序员发帖求助到。二面腾讯,其中一个算法题:64匹
面试官:你连RESTful都不知道我怎么敢要你?
面试官:了解RESTful吗? 我:听说过。 面试官:那什么是RESTful? 我:就是用起来很规范,挺好的 面试官:是RESTful挺好的,还是自我感觉挺好的 我:都挺好的。 面试官:… 把门关上。 我:… 要干嘛?先关上再说。 面试官:我说出去把门关上。 我:what ?,夺门而去 文章目录01 前言02 RESTful的来源03 RESTful6大原则1. C-S架构2. 无状态3.统一的接
求小姐姐抠图竟遭白眼?痛定思痛,我决定用 Python 自力更生!
点击蓝色“Python空间”关注我丫加个“星标”,每天一起快乐的学习大家好,我是 Rocky0429,一个刚恰完午饭,正在用刷网页浪费生命的蒟蒻...一堆堆无聊八卦信息的网页内容慢慢使我的双眼模糊,一个哈欠打出了三斤老泪,就在此时我看到了一张图片:是谁!是谁把我女朋友的照片放出来的!awsl!太好看了叭...等等,那个背景上的一堆鬼画符是什么鬼?!真是看不下去!叔叔婶婶能忍,隔壁老王的三姨妈的四表...
为啥国人偏爱Mybatis,而老外喜欢Hibernate/JPA呢?
关于SQL和ORM的争论,永远都不会终止,我也一直在思考这个问题。昨天又跟群里的小伙伴进行了一番讨论,感触还是有一些,于是就有了今天这篇文。 声明:本文不会下关于Mybatis和JPA两个持久层框架哪个更好这样的结论。只是摆事实,讲道理,所以,请各位看官勿喷。 一、事件起因 关于Mybatis和JPA孰优孰劣的问题,争论已经很多年了。一直也没有结论,毕竟每个人的喜好和习惯是大不相同的。我也看
SQL-小白最佳入门sql查询一
不要偷偷的查询我的个人资料,即使你再喜欢我,也不要这样,真的不好;
项目中的if else太多了,该怎么重构?
介绍 最近跟着公司的大佬开发了一款IM系统,类似QQ和微信哈,就是聊天软件。我们有一部分业务逻辑是这样的 if (msgType = "文本") { // dosomething } else if(msgType = "图片") { // doshomething } else if(msgType = "视频") { // doshomething } else { // doshom...
致 Python 初学者
欢迎来到“Python进阶”专栏!来到这里的每一位同学,应该大致上学习了很多 Python 的基础知识,正在努力成长的过程中。在此期间,一定遇到了很多的困惑,对未来的学习方向感到迷茫。我非常理解你们所面临的处境。我从2007年开始接触 python 这门编程语言,从2009年开始单一使用 python 应对所有的开发工作,直至今天。回顾自己的学习过程,也曾经遇到过无数的困难,也曾经迷茫过、困惑过。开办这个专栏,正是为了帮助像我当年一样困惑的 Python 初学者走出困境、快速成长。希望我的经验能真正帮到你
“狗屁不通文章生成器”登顶GitHub热榜,分分钟写出万字形式主义大作
一、垃圾文字生成器介绍 最近在浏览GitHub的时候,发现了这样一个骨骼清奇的雷人项目,而且热度还特别高。 项目中文名:狗屁不通文章生成器 项目英文名:BullshitGenerator 根据作者的介绍,他是偶尔需要一些中文文字用于GUI开发时测试文本渲染,因此开发了这个废话生成器。但由于生成的废话实在是太过富于哲理,所以最近已经被小伙伴们给玩坏了。 他的文风可能是这样的: 你发现,...
程序员:我终于知道post和get的区别
是一个老生常谈的话题,然而随着不断的学习,对于以前的认识有很多误区,所以还是需要不断地总结的,学而时习之,不亦说乎
《程序人生》系列-这个程序员只用了20行代码就拿了冠军
你知道的越多,你不知道的越多 点赞再看,养成习惯GitHub上已经开源https://github.com/JavaFamily,有一线大厂面试点脑图,欢迎Star和完善 前言 这一期不算《吊打面试官》系列的,所有没前言我直接开始。 絮叨 本来应该是没有这期的,看过我上期的小伙伴应该是知道的嘛,双十一比较忙嘛,要值班又要去帮忙拍摄年会的视频素材,还得搞个程序员一天的Vlog,还要写BU...
相关热词 c# plc s1200 c#里氏转换原则 c# 主界面 c# do loop c#存为组套 模板 c# 停掉协程 c# rgb 读取图片 c# 图片颜色调整 最快 c#多张图片上传 c#密封类与密封方法
立即提问