[Shoi2007]Vote \u5584\u610f\u7684\u6295\u7968 <\/p>\n
Time Limit:1000MS Memory Limit:65536K
Total Submit:59 Accepted:40<\/p>\n
Description <\/strong><\/p>\n \u5e7c\u513f\u56ed\u91cc\u6709n\u4e2a\u5c0f\u670b\u53cb\u6253\u7b97\u901a\u8fc7\u6295\u7968\u6765\u51b3\u5b9a\u7761\u4e0d\u7761\u5348\u89c9\u3002\u5bf9\u4ed6\u4eec\u6765\u8bf4\uff0c\u8fd9\u4e2a\u95ee\u9898\u5e76\u4e0d\u662f\u5f88\u91cd\u8981\uff0c\u4e8e\u662f\u4ed6\u4eec\u51b3\u5b9a\u53d1\u626c\u8c26\u8ba9\u7cbe\u795e\u3002\u867d\u7136\u6bcf\u4e2a\u4eba\u90fd\u6709\u81ea\u5df1\u7684\u4e3b\u89c1\uff0c \u4f46\u662f\u4e3a\u4e86\u7167\u987e\u4e00\u4e0b\u81ea\u5df1\u670b\u53cb\u7684\u60f3\u6cd5\uff0c\u4ed6\u4eec\u4e5f\u53ef\u4ee5\u6295\u548c\u81ea\u5df1\u672c\u6765\u610f\u613f\u76f8\u53cd\u7684\u7968\u3002\u6211\u4eec\u5b9a\u4e49\u4e00\u6b21\u6295\u7968\u7684\u51b2\u7a81\u6570\u4e3a\u597d\u670b\u53cb\u4e4b\u95f4\u53d1\u751f\u51b2\u7a81\u7684\u603b\u6570\u52a0\u4e0a\u548c\u6240\u6709\u548c\u81ea\u5df1\u672c\u6765\u610f\u613f\u53d1 \u751f\u51b2\u7a81\u7684\u4eba\u6570\u3002 Input <\/strong><\/p>\n \u7b2c\u4e00\u884c\u53ea\u6709\u4e24\u4e2a\u6574\u6570n\uff0cm\uff0c\u4fdd\u8bc1\u67092\u2264n\u2264300\uff0c1\u2264m\u2264n(n-1)\/2\u3002\u5176\u4e2dn\u4ee3\u8868\u603b\u4eba\u6570\uff0cm\u4ee3\u8868\u597d\u670b\u53cb\u7684\u5bf9\u6570\u3002\u6587\u4ef6\u7b2c\u4e8c\u884c\u6709n\u4e2a\u6574\u6570\uff0c\u7b2ci\u4e2a\u6574\u6570 \u4ee3\u8868\u7b2ci\u4e2a\u5c0f\u670b\u53cb\u7684\u610f\u613f\uff0c\u5f53\u5b83\u4e3a1\u65f6\u8868\u793a\u540c\u610f\u7761\u89c9\uff0c\u5f53\u5b83\u4e3a0\u65f6\u8868\u793a\u53cd\u5bf9\u7761\u89c9\u3002\u63a5\u4e0b\u6765\u6587\u4ef6\u8fd8\u6709m\u884c\uff0c\u6bcf\u884c\u6709\u4e24\u4e2a\u6574\u6570i\uff0cj\u3002\u8868\u793ai\uff0cj\u662f\u4e00\u5bf9\u597d\u670b\u53cb\uff0c\u6211\u4eec\u4fdd \u8bc1\u4efb\u4f55\u4e24\u5bf9i\uff0cj\u4e0d\u4f1a\u91cd\u590d\u3002 <\/p>\n Output <\/strong><\/p>\n \u53ea\u9700\u8981\u8f93\u51fa\u4e00\u4e2a\u6574\u6570\uff0c\u5373\u53ef\u80fd\u7684\u6700\u5c0f\u51b2\u7a81\u6570\u3002 <\/p>\n Sample Input <\/strong><\/p>\n 3 3 Sample Output <\/strong><\/p>\n 1<\/p>\n Hint <\/strong><\/p>\n \u5728\u7b2c\u4e00\u4e2a\u4f8b\u5b50\u4e2d\uff0c\u6240\u6709\u5c0f\u670b\u53cb\u90fd\u6295\u8d5e\u6210\u7968\u5c31\u80fd\u5f97\u5230\u6700\u4f18\u89e3<\/p>\n Source <\/strong><\/p>\n Day2 #include <vector> [Shoi2007]Vote \u5584\u610f\u7684\u6295\u7968 Time Limit:1000MS Memory Limit:65536KTotal Submit:59 Accepted:40 Description \u5e7c\u513f\u56ed\u91cc\u6709n\u4e2a\u5c0f\u670b\u53cb\u6253\u7b97\u901a\u8fc7\u6295\u7968\u6765\u51b3\u5b9a\u7761\u4e0d\u7761\u5348\u89c9\u3002\u5bf9\u4ed6\u4eec\u6765\u8bf4\uff0c\u8fd9\u4e2a\u95ee\u9898\u5e76\u4e0d\u662f\u5f88\u91cd\u8981\uff0c\u4e8e\u662f\u4ed6\u4eec\u51b3\u5b9a\u53d1\u626c\u8c26\u8ba9\u7cbe\u795e\u3002\u867d\u7136\u6bcf\u4e2a\u4eba\u90fd\u6709\u81ea\u5df1\u7684\u4e3b\u89c1\uff0c \u4f46\u662f\u4e3a\u4e86\u7167\u987e\u4e00\u4e0b\u81ea\u5df1\u670b\u53cb\u7684\u60f3\u6cd5\uff0c\u4ed6\u4eec\u4e5f\u53ef\u4ee5\u6295\u548c\u81ea\u5df1\u672c\u6765\u610f\u613f\u76f8\u53cd\u7684\u7968\u3002\u6211\u4eec\u5b9a\u4e49\u4e00\u6b21\u6295\u7968\u7684\u51b2\u7a81\u6570\u4e3a\u597d\u670b\u53cb\u4e4b\u95f4\u53d1\u751f\u51b2\u7a81\u7684\u603b\u6570\u52a0\u4e0a\u548c\u6240\u6709\u548c\u81ea\u5df1\u672c\u6765\u610f\u613f\u53d1 \u751f\u51b2\u7a81\u7684\u4eba\u6570\u3002 \u6211\u4eec\u7684\u95ee\u9898\u5c31\u662f\uff0c\u6bcf\u4f4d\u5c0f\u670b\u53cb\u5e94\u8be5\u600e\u6837\u6295\u7968\uff0c\u624d\u80fd\u4f7f\u51b2\u7a81\u6570\u6700\u5c0f\uff1f Input \u7b2c\u4e00\u884c\u53ea\u6709\u4e24\u4e2a\u6574\u6570n\uff0cm\uff0c\u4fdd\u8bc1\u67092\u2264n\u2264300\uff0c1\u2264m\u2264n(n-1)\/2\u3002\u5176\u4e2dn\u4ee3\u8868\u603b\u4eba\u6570\uff0cm\u4ee3\u8868\u597d\u670b\u53cb\u7684\u5bf9\u6570\u3002\u6587\u4ef6\u7b2c\u4e8c\u884c\u6709n\u4e2a\u6574\u6570\uff0c\u7b2ci\u4e2a\u6574\u6570 \u4ee3\u8868\u7b2ci\u4e2a\u5c0f\u670b\u53cb\u7684\u610f\u613f\uff0c\u5f53\u5b83\u4e3a1\u65f6\u8868\u793a\u540c\u610f\u7761\u89c9\uff0c\u5f53\u5b83\u4e3a0\u65f6\u8868\u793a\u53cd\u5bf9\u7761\u89c9\u3002\u63a5\u4e0b\u6765\u6587\u4ef6\u8fd8\u6709m\u884c\uff0c\u6bcf\u884c\u6709\u4e24\u4e2a\u6574\u6570i\uff0cj\u3002\u8868\u793ai\uff0cj\u662f\u4e00\u5bf9\u597d\u670b\u53cb\uff0c\u6211\u4eec\u4fdd \u8bc1\u4efb\u4f55\u4e24\u5bf9i\uff0cj\u4e0d\u4f1a\u91cd\u590d\u3002 Output \u53ea\u9700\u8981\u8f93\u51fa\u4e00\u4e2a\u6574\u6570\uff0c\u5373\u53ef\u80fd\u7684\u6700\u5c0f\u51b2\u7a81\u6570\u3002 Sample Input 3 31 0 01 21 33 2 Sample Output 1 Hint \u5728\u7b2c\u4e00\u4e2a\u4f8b\u5b50\u4e2d\uff0c\u6240\u6709\u5c0f\u670b\u53cb\u90fd\u6295\u8d5e\u6210\u7968\u5c31\u80fd\u5f97\u5230\u6700\u4f18\u89e3 Source Day2\u989d\u3002\u3002\u8fd9\u4e2a\u9898\u76ee\u663e\u7136\u53ef\u4ee5\u7528\u7f51\u7edc\u6d41\u89e3\u51b3\u3002\u3002\u4f46\u662f\u7ecfSeventh\u795e\u725b\u7684\u63d0\u9192\u3002\u3002\u6211\u4f7f\u7528\u968f\u673a\u5316AC\u4e86\u8fd9\u4e2a\u3002\u3002\u3002\u5c31\u662f\u968f\u673a\u4e00\u4e2a\u51b3\u7b56\u51fa\u6765\u3002\u3002\u7136\u540e\u628a\u80fd\u6700\u5927\u964d\u4f4e\u51b2\u7a81\u6570\u7684\u90a3\u4e2a\u4eba\u51b3\u7b56\u53cd\u8fc7\u6765\u3002\u3002\u4e0d\u65ad\u641e\u76f4\u5230\u5c40\u90e8\u6700\u4f18\u3002\u3002\u7ecf\u8fc7\u6d4b\u8bd5\u968f\u673a\u531610\u6b21\u4ee5\u4e0a\u4f1aTLE\u3002\u30023\u6b21\u5c31\u53ef\u4ee5AC\u56e7\u3002\u3002Code\uff1a #include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#include <set>#include <map>#include <cstring>#include <time.h>#define rep(i,n) for(int i=0;i<n;i++)const int inf=~0U>>1,maxn=300;using namespace std;int A[maxn],X[maxn],ans=inf,n,m;bool […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/308"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=308"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/308\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=308"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=308"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=308"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u6211\u4eec\u7684\u95ee\u9898\u5c31\u662f\uff0c\u6bcf\u4f4d\u5c0f\u670b\u53cb\u5e94\u8be5\u600e\u6837\u6295\u7968\uff0c\u624d\u80fd\u4f7f\u51b2\u7a81\u6570\u6700\u5c0f\uff1f <\/p>\n
1 0 0
1 2
1 3
3 2<\/p>\n
\u989d\u3002\u3002\u8fd9\u4e2a\u9898\u76ee\u663e\u7136\u53ef\u4ee5\u7528\u7f51\u7edc\u6d41\u89e3\u51b3\u3002\u3002\u4f46\u662f\u7ecfSeventh\u795e\u725b\u7684\u63d0\u9192\u3002\u3002\u6211\u4f7f\u7528\u968f\u673a\u5316AC\u4e86\u8fd9\u4e2a\u3002\u3002\u3002
\u5c31\u662f\u968f\u673a\u4e00\u4e2a\u51b3\u7b56\u51fa\u6765\u3002\u3002\u7136\u540e\u628a\u80fd\u6700\u5927\u964d\u4f4e\u51b2\u7a81\u6570\u7684\u90a3\u4e2a\u4eba\u51b3\u7b56\u53cd\u8fc7\u6765\u3002\u3002\u4e0d\u65ad\u641e\u76f4\u5230\u5c40\u90e8\u6700\u4f18\u3002\u3002
\u7ecf\u8fc7\u6d4b\u8bd5\u968f\u673a\u531610\u6b21\u4ee5\u4e0a\u4f1aTLE\u3002\u30023\u6b21\u5c31\u53ef\u4ee5AC\u56e7\u3002\u3002
Code\uff1a<\/p>\n
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=300;
using namespace std;
int A[maxn],X[maxn],ans=inf,n,m;
bool E[maxn][maxn]={};
void Random()
{
rep(i,n)X[i]=rand()%2;
while(true)
{
int ch,Min=inf,f=-1;
rep(i,n)
{
ch=0;X[i]^=1;
if(X[i]^A[i])ch++;else ch–;
rep(j,n)if(E[i][j])
{
if(X[i]^X[j])ch++;
else ch–;
}
X[i]^=1;
if(ch<Min){Min=ch;f=i;}
}
if(Min>=0)break;
X[f]^=1;
}
int ret=0;
rep(i,n)
{
if(X[i]^A[i])ret+=2;
rep(j,n)if(E[i][j]&&X[i]^X[j])
ret++;
}
ret\/=2;
ans=min(ret,ans);
}
int main()
{
\/\/freopen("in","r",stdin);
cin>>n>>m;rep(i,n)cin>>A[i];
int s,t;
rep(i,m)
{
scanf("%d%d",&s,&t);–s;–t;
E[s][t]=E[t][s]=true;
}
rep(i,3)Random();
cout<<ans<<endl;
}<\/p>\n","protected":false},"excerpt":{"rendered":"