题解：
T1:收益如果一个人同时支持两个议题，那么它一定会入选。接下来按01和10两两配对接着取，配完之后剩下的都和00无异，从大往小选即可。
O(N log N)
# include <bits/stdc++.h>
using namespace std;
namespace Base{
# define mr make_pair
typedef long long ll;
typedef double db;
const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
const ll infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
template<typename T> void read(T &x){
x = 0; int fh = 1; double num = 1.0; char ch = getchar();
while (!isdigit(ch)){ if (ch == '-') fh = -1; ch = getchar(); }
while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
if (ch == '.'){
ch = getchar();
while (isdigit(ch)){num /= 10; x = x + num * (ch - '0'); ch = getchar();}
}
x = x * fh;
}
template<typename T> void chmax(T &x, T y){x = x < y ? y : x;}
template<typename T> void chmin(T &x, T y){x = x > y ? y : x;}
}
using namespace Base;
const int N = 1000010;
int n, val[4][N], num[4], ans;
bool cmp(int x, int y){
return x > y;
}
int main(){
freopen("debate.in", "r", stdin);
freopen("debate.out", "w", stdout);
read(n);
for (int i = 1; i <= n; i++){
int x, v, c;
read(x); read(v);
if (x == 11) c = 0;
if (x == 10) c = 1;
if (x == 01) c = 2;
if (x == 00) c = 3;
val[c][++num[c]] = v;
}
sort(val[1] + 1, val[1] + num[1] + 1, cmp);
sort(val[2] + 1, val[2] + num[2] + 1, cmp);
int mn = min(num[1], num[2]);
for (int i = 1; i <= mn; i++)
ans = ans + val[1][i] + val[2][i];
for (int i = mn + 1; i <= num[1]; i++) val[3][++num[3]] = val[1][i];
for (int i = mn + 1; i <= num[2]; i++) val[3][++num[3]] = val[2][i];
sort(val[3] + 1, val[3] + num[3] + 1, cmp);
for (int i = 1; i <= num[0]; i++)
ans = ans + val[0][i] + val[3][i];
printf("%d\n", ans);
return 0;
}
T2:不难发现当K=8时可行的合法解就超过100000，所以解是非常多的，直接爆搜即可。
O(能过)
#include <cstdio>
#define filein "hexodoku"
void prepare( )
{
freopen( filein ".in", "r", stdin );
freopen( filein ".out", "w", stdout );
}
#include <cmath>
#include <cassert>
#include <memory.h>
#include <vector>
#include <string>
#include <ctime>
#include <algorithm>
#include <functional>
using namespace std;
#define fo(a,b,c) for(a=(b);a<(c);++a)
#define fr(a,b) fo(a,0,(b))
#define fi(a) fr(i,(a))
#define fj(a) fr(j,(a))
#define fk(a) fr(k,(a))
#define _(a,b) memset((a),(b),sizeof(a))
#define __(a) _((a),0)
const int dx[] = { 1, 0, -1, -1, 0, 1, 0 };
const int dy[] = { 0, 1, 1, 0, -1, -1, 0 };
const int MAXN = 7;
const int MAXF = 32;
char f[MAXN][MAXN + 1];
char m[MAXF];
char ansm[MAXF];
int ans;
vector<pair< int, int> > v[MAXN][MAXN];
vector<pair< int, int> > coord;
int p[MAXF][MAXF];
int pn[MAXF];
int need;
int MAXID;
int K, N;
bool test( )
{
if ( ++ ans < N )
return false;
memcpy( ansm, m, sizeof( m ) );
return true;
}
int makemask( const int &id )
{
int i;
int res = 0;
int *pp = p[id];
int ppn = pn[id];
fi( ppn )
{
int cv = m[pp[i]];
if ( cv >= 0 )
res |= 1 << cv;
}
return res;
}
bool brute( int id )
{
if ( id == MAXID )
return test( );
if ( m[id] >= 0 )
return brute( id + 1 );
int mask = makemask( id );
int i;
fi( K )
{
if ( mask & ( 1 << i ) )
continue;
m[id] = i;
if ( brute( id + 1 ) )
return true;
m[id] = -1;
}
return false;
}
void buildgraph( )
{
_( f, -1 );
// fprintf( stderr, "Build started\n" );
int i, j, k;
fi( 7 ) if ( i <= 7 )
{
int y = 3;
int x = 3;
if ( i < 6 )
{
y += dy[i] * 2 + dy[( i + 4 ) % 6];
x += dx[i] * 2 + dx[( i + 4 ) % 6];
}
fj( 7 )
{
int cx = x + dx[j];
int cy = y + dy[j];
f[cy][cx] = 0;
fk( 7 ) if ( k != j )
{
v[cy][cx].push_back( make_pair( y + dy[k], x + dx[k] ) );
}
}
}
int d;
fi( MAXN ) fj( MAXN ) if ( !f[i][j] ) fr( d, 6 ) fo( k, 1, MAXN )
{
int cy = i + dy[d] * k;
int cx = j + dx[d] * k;
if ( cx < 0 || cy < 0 || cx >= MAXN || cy >= MAXN || f[cy][cx] )
break;
v[i][j].push_back( make_pair( cy, cx ) );
}
MAXID = 0;
fi( MAXN ) fj( MAXN )
{
if ( f[i][j] == 0 )
{
coord.push_back( make_pair( i, j ) );
f[i][j] = MAXID++;
}
}
fi( MAXID )
{
vector<pair<int, int> > &tw = v[coord[i].first][coord[i].second];
sort( tw.begin( ), tw.end( ) );
tw.resize( unique( tw.begin( ), tw.end( ) ) - tw.begin( ) );
fj( (int)tw.size( ) )
{
p[i][pn[i]++] = f[tw[j].first][tw[j].second];
}
}
// fprintf( stderr, "Build finished\n" );
}
void readfield( )
{
// fprintf( stderr, "Read started\n" );
scanf( "%d %d", &K, &N );
_( m, -1 );
int i, j;
fi( MAXID )
{
int temp;
scanf( "%d", &temp );
if ( temp == 0 )
m[i] = -1;
else
m[i] = temp - 1;
}
// fprintf( stderr, "Read finished\n" );
}
void solve( )
{
clock_t st = clock( );
// fprintf( stderr, "Solve started\n" );
if ( brute( 0 ) )
{
printf( "Found\n" );
memcpy( m, ansm, sizeof( m ) );
bool first = true;
int i, j;
fi( MAXID )
{
if ( first ) first = false;
else printf( " " );
printf( "%d", m[i] + 1 );
}
printf( "\n" );
/*
fi( MAXN )
{
fj( i ) fprintf( stderr, " " );
fj( MAXN )
{
if ( f[i][j] >= 0 )
{
fprintf( stderr, "%2d", m[f[i][j]] );
}
else
fprintf( stderr, " -" );
}
fprintf( stderr, "\n" );
}
*/ }
else
{
printf( "No way\n" );
}
st = clock( ) - st;
}
int main( )
{
prepare( );
int i, j, k;
buildgraph( );
readfield( );
solve( );
return 0;
}
T3:50分：我们可以用logN的时间判断出相邻两个点是否同色，宽搜即可。宽搜后可以发现10000以内最大的连通块的面积只有2*10^7级别。
O(答案)
100分：考虑把点分类：
只和下方连通的-1，和右方连通的-1（这两类等价）
同时和下方和右方连通的-1
只和下方连通的1，和右方连通的1（这两类等价）
同时和下方和右方连通的1
对于其余的点，完全在内部的不用讨论，最左和最上的都是1，且它们为infinity，也不要讨论。
在扩展时同时维护这些点的数量，和要求的点所在的位置，具体时间见代码。
O(logN)
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define TASKNAME "area"
#define INT64 "%lld"
typedef long long int64;
enum STATE {P0, P1, P2D, P2R, M1, M2D, M2R, STATE_NUM};
const int DX = STATE_NUM, DY = STATE_NUM * 2;
int main (void)
{
int i, x, y, st;
int64 area, p0, p1, p2, m1, m2, p0n, p1n, p2n, m1n, m2n;
freopen (TASKNAME ".in", "rt", stdin);
freopen (TASKNAME ".out", "wt", stdout);
while (scanf (" %d %d", &x, &y) != EOF)
{
area = p0 = 1; p1 = p2 = m1 = m2 = 0;
st = P0;
for (i = 0; i < 31; i++)
{
p0n = p0 * 3 + p1 + p2 * 2;
p1n = m1;
p2n = p1 + p2 + m2;
m1n = p0 + p1 + m1 * 2 + m2 * 2;
m2n = p2 + m2;
switch (st + DX * ((x >> i) & 1) + DY * ((y >> i) & 1))
{
case P0:
case P1:
case P2D:
case P2R:
case P0 + DX:
case P0 + DY:
area = p0n;
st = P0;
break;
case M1 + DX + DY:
st = P1;
break;
case P1 + DY:
case P2D + DY:
case M2D + DX + DY:
st = P2D;
break;
case P1 + DX:
case P2R + DX:
case M2R + DX + DY:
st = P2R;
break;
case M1 + DX:
case M2D + DX:
case M1 + DY:
case M2R + DY:
case P0 + DX + DY:
area = m1n - p1;
// fallthrough
case P1 + DX + DY:
st = M1;
break;
case M2D + DY:
case P2D + DX + DY:
st = M2D;
break;
case M2R + DX:
case P2R + DX + DY:
st = M2R;
break;
default:
st = STATE_NUM; // isolated component
break;
}
p0 = p0n;
p1 = p1n;
p2 = p2n;
m1 = m1n;
m2 = m2n;
if (st == STATE_NUM) break;
}
if (st == P0) printf ("infinity\n");
else printf (INT64 "\n", area);
}
return 0;
}
京公网安备 11010502036488号