不知两位版主为何现在不做题了，你们的帖子让我学到了很多东西，希望这个帖子继续下去，毕竟OJ上的题还有很多，我有能力的话会跟大家一起做题

Problem 1248 - 密码 Time Limit: 1000MS   Memory Limit: 65536KB
最近某些人在搞密码学。

——这是背景
现在有一个情况，就是LHM给了LBW一段密文，并说明：定义Si表示字符串S[0..i],即{Si}为该密文的所有前缀字符串，再定义F(S)为字符串S中最长的同时为S的不包含最后一个字符的前缀和不包含第一个字符的后缀的字符串，例如F(“aabbaa”) = aa (“aa” 同时为其前缀和后缀)。现在求Max(F(Si))。
Input多组数据，每组数据占一行，为一个长度为L的字符串（1 <= L <=1000000）
Output每组输出一行，为其最长子串（没有就输出No）。
Sample Input
aabbaa
ab
Sample Output
aa
No
分析：参考KMP算法中next函数值的求解方法，速度较快。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 1000003
int num[MAX]; char s[MAX];
int main()
{
    while(scanf("%s", s) != EOF)
    {
        int len = strlen(s);
        int max = 0;
        int i = 0; int j = -1;
        while(i <= len)
        {
            if(j == -1 || s[i] == s[j])
            {
                ++i; ++j; num[i-1] = j;
                if(j > max) max = j;
            }
            else
            {
                if(j == 0)
                j = -1;
                else j = num[j-1];
            }
        }   
        if(max == 0) printf("NO");
        else for(int i = 0; i < max; ++i) printf("%c", s[i]);
        printf("\n");
        memset(s, 0, sizeof(s)); memset(num, 0, sizeof(num));
    }
}

 

看了一下1015楼主的题解，感叹其位运算的能力，由于不擅长位运算，写了个水代码，但是在空间和时间上略优于楼主，思想相同。
贴一下代码：

#include <stdio.h>
int main() {
    int num = 0; double max[35], min[35];
    while(scanf("%d", &num) != EOF) {   
        for(int i = 0; i < 35; ++i) {
        max[i] = -1e10; min[i] = 1e10;
        }
        for(int i = 0; i < num; ++i) {
            double a, b, c, d, e;   
            scanf("%lf%lf%lf%lf%lf", &a, &b, &c, &d, &e);
            int j = 0;
            for(int A = -1; A < 2; A+=2)
            for(int B = -1; B < 2; B+=2)
            for(int C = -1; C < 2; C+=2)
            for(int D = -1; D < 2; D+=2)
            for(int E = -1; E < 2; E+=2) {
                double temp;
                temp = A*a + B*b + C*c + D*d + E*e;
                if(max[j] < temp) max[j] = temp;
                if(min[j] > temp) min[j] = temp;
                j++;
            }
        }
        double result = 0.0;
        for(int i = 0; i < 32; ++i) {
            if(result < max[i]-min[i])
            result = max[i]-min[i];
        }
        printf("%.2lf\n", result);
    }
    return 0;
}

看不懂1006的代码，位运算很蛋疼啊

版主 你好，有没有西电的OJ所有题的汇总呢，我最近在准备ACM校赛，想好好练练手，，能发给我吗，谢谢了。。。。十分感谢

版主，你好，我做了下第Problem 1174 - 素数时间 这个题，我自己测试是对的，但是提交后死活说输出不对，求帮忙看看代码：

Description  素数对ACM里的数论来说永远是一个最美丽的话题，现在又到了素数时间了。现在给你一个整数m(4 <=m<= 10^18)，那么能不能找出m的一个素因子p是比n(2 <= n <= 10^6)小的呢？
Description  素数对ACM里的数论来说永远是一个最美丽的话题，现在又到了素数时间了。现在给你一个整数m(4 <=m<= 10^18)，那么能不能找出m的一个素因子p是比n(2 <= n <= 10^6)小的呢？

Input多组数据，每行两个数字m和n，以0 0结束Output如果存在，输出BAD p(这个素因子)，如果存在多个输出最小的;如果不存在，就输出GOOD吧。（如样例所示）Sample Input143 10
143 20
667 20
667 30
2573 30
2573 40
0 0
Sample OutputGOOD
BAD 11
GOOD
BAD 23
GOOD
BAD 31


#include<cstdio>
#include<cmath>
#include<iostream>
#include <vector>
using namespace std;
int main()
{
    long long int k;
    double m,m2,m1;
    long int n;
    int cnt=0;
    int i;
    vector<long int> N;
    vector<double> M1;
    do
    {
        cin>>m>>n;
        M1.push_back(m);
        N.push_back(n);
    }while((m!=0)&&(n!=0));
        
    for(vector<int> ::size_type ix=0;ix!=(N.size()-1);++ix)
    {
         int cnt=0;    //reset
        if(M1[ix]>= 4 && M1[ix]<= 10e18 && N[ix]>= 2 && N[ix]<= 1000000)
        {
            m2=M1[ix];
            for(m1=5;m1<=N[ix];m1++)
            {
                k=sqrt(m1);
                for(i=2;i<=k;i++)
                    if(((long long int)m1)%i==0)  //判读其是否为素数  
                    {
                        break;
                    }   
                    if((i>k)&&(m1<=N[ix])&&(m1>=2))
                    {
                        if(((long long)M1[ix])%((long long)m1)==0)
                        {
                            cout<<"BAD"<<"\t"<<m1<<endl;
                            cnt++;
                            cnt=cnt%2;
                            break;
                        }
                    }
                    
            }
            if(cnt==0)
            {
                cout<<"GOOD"<<endl;
               
            }
        }
        }
   
    return 0;
}

用c很简单，你看看。

#include <stdio.h>
#include <math.h>
int isprime(long long int x)
{
    long long int i;
    if (x==2||x==3) return 1;
    if (x>=4)
    {
        for (i=2; i<=(int)sqrt((double)x); i++)
            if (x%i==0) return 0;
    }
    return 1;
}
int main()
{
    long long int m = 1, n = 1, i;
    while (m&&n)
    {
        scanf("%lld %lld", &m, &n);
        if (m&&n)
        {
            for (i=2; i<n; i++)
            {
                if ((m%i==0)&&isprime(i)) 
                {
                    printf("BAD %lld\n", i);
                    break;
                }
            }
            if (i>=n) printf("GOOD\n");
        }
    }
    return 0;
}

mark，有时间细看。

我有个不太成熟的想法，我觉得可以采用深度优先遍历来求取连通分量，然后将舒适度从小到大排列 在不构建最小生成树的前提下
1 若现在所需的资源小于 该岛上所有的资源 则从最小舒适度开始往上删边 每删一条边 用深度优先遍历来求取连通分量 始终保证连通分量为一 若不满足，
则取消删除这条边 并保证权值不变 继续往上走 ；若满足删除边的条件，所选资源减去该边的权值，将该边权值赋为0；若最终结果为所需资源大于岛上资源 则失败；否则 从小到达遍历边数组找到第一个权值不为0 的边，并返回该边的舒适度；
2 若所需资源大于岛上资源，则按权值从大到小删除边 则原理同上，最终得出结论
不知道 对不对？
#include<iostream>
#include<algorithm>
using namespace std;
bool visit [510];
int e[510][510],n;
void dfs(int node)
{
    visit[node]=true;
    for(int i=0;i<n;i++)
    {
        if(e[node][i]>0&&visit[i]==false)
        dfs(i);
    }
}
int countint()
{
    int cnt=0;
    fill(visit,visit+510,false);
    for(int i=0;i<n;i++)
    {
        if(visit[i]==false)
        {
            dfs(i);
            cnt++;
        }
    }
    return cnt;
}
typedef struct edge
{
    int s,e,w,v;
};
int cmp(edge a,edge b){return a.v<b.v;}
int main()
{
int m,r,temp,r1=0,cnt2,q,t;
cin>>n>>m>>r;
edge s[m];
for(int i=0;i<m;i++)
{
    cin>>s[i].s>>s[i].e>>s[i].w>>s[i].v;
    e[s[i].s][s[i].e]=e[s[i].e][s[i].s]=s[i].w;
    r1+=s[i].w;
}
sort(s,s+m,cmp);
if(r1<=r){
for(int i=0;i<m;i++)
{
  t=e[s[i].s][s[i].e];
  e[s[i].s][s[i].e]=e[s[i].e][s[i].s]=0;
  if(countint()>1)
  {
    e[s[i].s][s[i].e]=e[s[i].e][s[i].s]=s[i].w;
  }
  else
  {
    r1-=s[i].w;
    s[i].w=0;
}
}
if(r1>r)
{
    cout<<-1<<endl;
}
else
{
for(int i=0;i<m;i++)
{
    if(s[i].w)
    {
        cout<<s[i].v<<endl;
        break;
    }
}
}
}
else
{
for(int i=m-1;i>=0;i--)
    {
  t=e[s[i].s][s[i].e];
  e[s[i].s][s[i].e]=e[s[i].e][s[i].s]=0;
  if(countint()>1)
  {
    e[s[i].s][s[i].e]=e[s[i].e][s[i].s]=s[i].w;
  }
  else
  {
    r1-=s[i].w;
    s[i].w=0;
}
}
if(r1<=r)
    for(int i=0;i<m;i++)
{
    if(s[i].w)
    {
        cout<<s[i].v;
        break;
    }
}
    else
        cout<<-1<<endl;
}
}
突然想到的 不知道对不对 第二个判断貌似有点问题，应该按权值从大到小排序，然后删边 只是数据比较巧合 舒适度和权值恰巧都为最大
不知道对不对 有可能错了 我觉得这样就避免再构造最小生成树