lxhgww鏈榪戣糠涓婁簡涓嬈炬父鎴忥紝鍦ㄦ父鎴忛噷錛屼粬鎷ユ湁寰堝鐨勮澶囷紝姣忕瑁呭閮芥湁2涓睘鎬э紝榪欎簺灞炴х殑鍊肩敤[1,10000]涔嬮棿鐨勬暟琛ㄧず銆傚綋浠栦嬌鐢ㄦ煇縐嶈澶囨椂錛屼粬鍙兘浣跨敤璇ヨ澶囩殑鏌愪竴涓睘鎬с傚茍涓旀瘡縐嶈澶囨渶澶氬彧鑳戒嬌鐢ㄤ竴嬈°?br>娓告垙榪涜鍒版渶鍚庯紝lxhgww閬囧埌浜嗙粓鏋乥oss錛岃繖涓粓鏋乥oss寰堝鎬紝鏀誨嚮浠栫殑瑁呭鎵浣跨敤鐨勫睘鎬у煎繀欏諱粠1寮濮嬭繛緇掑鍦版敾鍑伙紝鎵嶈兘瀵筨oss浜х敓浼ゅ銆備篃灝辨槸璇翠竴寮濮嬬殑鏃跺欙紝lxhgww鍙兘浣跨敤鏌愪釜灞炴у間負(fù)1鐨勮澶囨敾鍑籦oss錛岀劧鍚庡彧鑳戒嬌鐢ㄦ煇涓睘鎬у間負(fù)2鐨勮澶囨敾鍑籦oss錛岀劧鍚庡彧鑳戒嬌鐢ㄦ煇涓睘鎬у間負(fù)3鐨勮澶囨敾鍑籦oss……浠ユ綾繪帹銆?br>鐜板湪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;
}
]]>
鍐呴儴涓嶅寘鍚?鐨勬渶澶х煩闃靛拰.
#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;
}
]]>