C++博客-elementlzhttp://www.cppblog.com/elementlz/zh-cnThu, 09 Apr 2026 06:28:44 GMTThu, 09 Apr 2026 06:28:44 GMT60SCTC2010 - 游戏http://www.cppblog.com/elementlz/archive/2010/04/15/112657.htmlEleMenTLzEleMenTLzThu, 15 Apr 2010 05:31:00 GMThttp://www.cppblog.com/elementlz/archive/2010/04/15/112657.htmlhttp://www.cppblog.com/elementlz/comments/112657.htmlhttp://www.cppblog.com/elementlz/archive/2010/04/15/112657.html#Feedback0http://www.cppblog.com/elementlz/comments/commentRss/112657.htmlhttp://www.cppblog.com/elementlz/services/trackbacks/112657.html
lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。
游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。
现在lxhgww想知道他最多能连续攻击boss多少次？
对于30%的数据，保证N<=1000
对于100%的数据，保证N<=1000000
#include<iostream>
#define MAXM 1000001
#define MAXN 1000001
#define MAXNANS 10000
using namespace std;
int a,b,n,tot,Tnow[MAXM],Ty[MAXM],pre[MAXM];
int head;
int from[MAXN];
bool visit[MAXN];
int Happen[MAXN];
bool find(int x){
    int mark = Tnow[x];
    while (mark > 0)
        {
            if (!visit[Ty[mark]])
                {
                    visit[Ty[mark]] = true;
                    Happen[++head] = Ty[mark];
                    if ((!from[Ty[mark]]) || (find(from[Ty[mark]])))
                        {
                            from[Ty[mark]] = x;
                            return true;
                        }
                }
            mark = pre[mark];
        }
    return false;
    }
void cnt(int x,int y){
     tot++;
     pre[tot] = Tnow[x];
     Tnow[x] = tot;
     Ty[tot] = y;
}
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    cin>>n;
    tot = 0;
    for (int i=1;i<=n;i++)
        {
            cin>>a>>b;
            cnt(a,i+MAXNANS);
            cnt(b,i+MAXNANS);
        }
    int Answer ;
    memset(visit,false,sizeof(visit));
    for (int i=1;i<=n;i++)
        {
            head = 0;
            if (!find(i))
            {
                    Answer = i - 1;
                    break;
                }
            for (int i=1;i<=head;i++)
                visit[Happen[i]] = false;
        }
    printf("%d\n",Answer);
    return 0;
}



EleMenTLz 2010-04-15 13:31 发表评论
]]>Candy.http://www.cppblog.com/elementlz/archive/2010/04/14/112589.htmlEleMenTLzEleMenTLzWed, 14 Apr 2010 14:50:00 GMThttp://www.cppblog.com/elementlz/archive/2010/04/14/112589.htmlhttp://www.cppblog.com/elementlz/comments/112589.htmlhttp://www.cppblog.com/elementlz/archive/2010/04/14/112589.html#Feedback0http://www.cppblog.com/elementlz/comments/commentRss/112589.htmlhttp://www.cppblog.com/elementlz/services/trackbacks/112589.html
内部不包含0的最大矩阵和.
#include<cstdio>
#include<algorithm>
#define maxn 1001
#define maxm 1001
#define INF 0x7fffffff
using namespace std;
int n,m;
int sum[maxn][maxm];
int l[maxn][maxn],r[maxn][maxn],h[maxn][maxn],v[maxn][maxn];
int L[maxn][maxn],R[maxn][maxn];
int getsum(int a,int b,int c,int d){
    return (sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1]);
    }
int main(){
    freopen("Candy.in","r",stdin);
    freopen("Candy.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            {
                scanf("%d",&v[i][j]);
                sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+v[i][j];
            }
    for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
                if (v[i][j]!=0)
                    l[i][j] = l[i][j-1]+1;
            for (int j=m;j>=1;j--)
                if (v[i][j]!=0)
                    r[i][j] = r[i][j+1]+1;

        }
    for (int i=1;i<=m;i++)
        h[1][i] = 0;
    memset(L,63,sizeof(L));
    memset(R,63,sizeof(R));
    int Answer = -INF;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (v[i][j]!=0)
            {
                h[i][j] = h[i-1][j]+1;
                L[i][j] = min ( l[i][j] , L[i-1][j]);
                R[i][j] = min ( r[i][j] , R[i-1][j]);
                Answer = max ( Answer , getsum (i-h[i][j]+1,j-L[i][j]+1,i,j+R[i][j]-1) );
            }
    printf("%d\n",Answer);
    return 0;
}



EleMenTLz 2010-04-14 22:50 发表评论
]]>