A
题目链接：http://www.ifrog.cc/acm/problem/1111
分析：容易发现本题就是排序不等式， 将A数组与B数组分别排序之后， 答案即N∑i=1Ai×Bi
此题有坑，反正据我提交而言，一直RE，之后发现两个地方会出错，一是定义数组要放在main函数之前，第二是ans+=1LL*a[i]*b[i],如果少了1LL,结果肯定WA，这就是此题的亮点所在！
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
const int MAXN = ;
int n ;
int a[MAXN], b[MAXN] ;
int main() {
scanf("%d", &n) ;
for (int i = ; i <= n; i ++) scanf("%d", &a[i]) ;
for (int i = ; i <= n; i ++) scanf("%d", &b[i]) ;
sort(a + , a + n + ) ;
sort(b + , b + n + ) ;
LL ans = ;
for (int i = ; i <= n; i ++) ans += 1LL * a[i] * b[i] ;
cout << ans << endl ;
}
B
题目链接：http://www.ifrog.cc/acm/problem/1112
分析：
一个显然的想法是每一次二分加入到第几个数的时候， 混乱度超过M， 然后暴力检验， 复杂度显然可以是O(N2logN)
级别
我们可以换一种二分方式
令当前左端点为L
， 我们先找到一个最小的K， 使得[L,L+2K)这个区间混乱度超过M
然后右端点在[L+2K−1,L+2K)
中二分即可
考虑每删去至少2K−1
个数， 所需要的时间复杂度最大为O(2KKlogN)
故总复杂度为O(Nlog2N)
#include <bits/stdc++.h> using namespace std ; int n ; typedef long long LL ; LL M ; const int MAXN = ; int a[MAXN] ; int ps[MAXN], p[MAXN], cnt[MAXN], v[MAXN];
bool vis[MAXN] ; bool check(int l, int r) {
for (int i = l; i <= r; i ++) p[i] = a[i] ;
sort(p + l, p + r + ) ;
LL ans = ;
for (int i = l; i <= r; i ++) {
ans += 1LL * p[i] * v[i - l + ] ;
}
return ans <= M ;
} int main() {
cin >> n >> M ;
for (int i = ; i <= n; i ++) scanf("%d", &a[i]) ;
for (int i = ; i <= n; i ++) scanf("%d", &v[i]) ;
int l = , r = ;
for (; l <= n;) {
int last = , lastp = r - ;
for (; check(l, r) && lastp < r; lastp = r , r = min(n, r + last), last <<= ) ;
if (lastp == r) break ;
int lp = lastp + , rp = r ;
while (lp < rp) {
int mid = ((lp + rp) >> ) ;
if (!check(l, mid)) rp = mid ;
else lp = mid + ;
}
cnt[lp] ++ ;
l = lp + , r = l ;
}
for (int i = ; i <= n; i ++) {
cnt[i] += cnt[i - ] ;
printf("%d", cnt[i]) ;
if (i < n) putchar(' ') ;
}
putchar() ;
}
C
题目链接：http://www.ifrog.cc/acm/problem/1113
分析：
注意到， K条路径两两相交的充要条件是这K
条路径有一段公共路径。
对于一条路径， 点数-边数恒为1
所以我们可以算出所有可能的情况中， K
条路径的公共点的个数 减去K
条路径的公共边的条数， 即为答案
我们可以枚举每一个点以及每一条边的贡献， 对于一个点来说， 它的贡献就是所有经过它的路径条数的K
次方，边同理
复杂度O(NlogK)
， 瓶颈在于快速幂
#include <bits/stdc++.h> #define MOD 1000000007 #ifdef WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif using namespace std ; int n, K ; typedef long long LL ; int qpow(int a, int b) {
int ret = ;
for (; b; b >>= , a = 1LL * a * a % MOD) if (b & ) ret = 1LL * ret * a % MOD ;
return ret ;
} const int MAXN = ; int siz[MAXN], fa[MAXN]; vector<int> g[MAXN]; int main() {
scanf("%d%d", &n, &K) ;
for (int i = ; i <= n; i ++) scanf("%d", &fa[i]) ;
for (int i = n; i; i --) {
siz[i] ++ ;
siz[fa[i]] += siz[i] ;
g[fa[i]].push_back(i) ;
}
int ans = ;
for (int i = ; i <= n; i ++) {
int t = 1LL * siz[i] * (n - siz[i]) % MOD ;
ans = (ans - qpow(t, K) + MOD) % MOD ;
}
for (int i = ; i <= n; i ++) {
int t = ;
for (int j = ; j < g[i].size(); j ++) {
t += 1LL * siz[g[i][j]] * (n - siz[g[i][j]] - ) % MOD ;
t %= MOD ;
}
t += 1LL * (siz[i] - ) * (n - siz[i]) % MOD ;
t %= MOD;
t = 1LL * t * ((MOD + ) / ) % MOD ;
t += n ;
t %= MOD ;
ans += qpow(t, K) ;
ans %= MOD ;
}
printf("%d\n", ans) ;
}
D
题目链接：http://www.ifrog.cc/acm/problem/1114
分析：
记SMN 为左边N个点， 右边M
个点的完全二分图生成树个数
答案即SKN−K×(N−1K−1)
， 证明显然， 因为把树上的点按照奇偶分层，即得到一个二分图， 每一棵树都对应了这个完全二分图的一个生成树
SMN=NM−1×MN−1
， 暴力用Matrix−Tree可以消元得到这个结论。
#include <bits/stdc++.h>
#define MOD 998244353
using namespace std ;
int n, k;
int qpow(int a, int b) {
int ret = ;
for (; b; b >>= , a = 1LL * a * a % MOD) if (b & ) ret = 1LL * ret * a % MOD ;
return ret ;
}
int C(int n, int m) {
int ans = ;
for (int i = ; i <= m; i ++) {
ans = 1LL * ans * (n - i + ) % MOD * qpow(i, MOD - ) % MOD ;
}
return ans ;
}
int main() {
scanf("%d%d", &n, &k) ;
n -= k ;
int ans = 1LL * qpow(n, k - ) * qpow(k, n - ) % MOD ;
ans = 1LL * ans * C(n + k - , k - ) % MOD ;
printf("%d\n", ans) ;
}
E
题目链接：http://www.ifrog.cc/acm/problem/1115
分析：
#define OPENSTACK #include <bits/stdc++.h>
#define MAXN 100010
#define Q 322
#define INF ~0ULL using namespace std; int n , m , cnt , a[ MAXN ] , tag[ MAXN ] , caocoacao[ MAXN ] , up[ MAXN ] , vis[ MAXN ];
int gandan [ MAXN ] , fa[ MAXN ] , size[ MAXN ] , son[ MAXN ] , xxxxxx[ MAXN ];
unsigned char left_bit[] , ssssssss[];
unsigned int wocaonimabis[][ MAXN ] , f[][] , lastans; struct wocaonima
{
unsigned long long bit[];
void clear()
{
memset( bit , , sizeof( bit ) );
}
void operator |= ( const wocaonima & rhs )
{
for( register int i = ; i <= ; i++ )
bit[i] |= rhs.bit[i];
}
void operator |= (const int x)
{
bit[x >> ] |= 1ll << ( x & );
}
inline int find( unsigned char k )
{
int len = , v[];
register unsigned int x = ;
for( register int i = ; i <= ; i++ )
{
v[] = bit[i] & , v[] = ( bit[i] >> ) & , v[] = ( bit[i] >> ) & , v[] = ( bit[i] >> );
for( register char j = ; j <= ; j++ )
if( v[j] == ) len += ;
else
{
//if( len + left_bit[ v[j] ] ) cerr << " " << len + left_bit[ v[j] ] << endl;
x += wocaonimabis[k][ len + left_bit[ v[j] ] ];
x += f[k][ v[j] ];
len = ssssssss[ v[j] ];
}
}
return x;
}
} ans; wocaonima BIT[Q + ][Q + ];
vector < int > linker[ MAXN ]; #define cur linker[x][i] void dfs1( int x )
{
size[x] = ;
for( int i = ; i < linker[x].size() ; i++ )
if( cur != fa[x] )
{
fa[ cur ] = x , gandan [ cur ] = gandan [x] + ;
dfs1( cur ) , size[x] += size[ cur ];
if( size[ cur ] > size[ son[x] ] ) son[x] = cur;
}
} void dfs2( int x , int t )
{
xxxxxx[x] = t;
if( son[x] ) dfs2( son[x] , t );
for( int i = ; i < linker[x].size() ; i++ )
if( cur != fa[x] && cur != son[x] )
dfs2( cur , cur );
} inline int lca( int a , int b )
{
while( xxxxxx[a] != xxxxxx[b] )
{
if( gandan [ xxxxxx[a] ] < gandan [ xxxxxx[b] ] ) swap( a , b );
a = fa[ xxxxxx[a] ];
}
return gandan [a] < gandan [b] ? a : b;
} #undef cur struct io
{
char ibuf[ << ] , * s , obuf[ << ] , * t;
int a[];
io() : t( obuf )
{
fread( s = ibuf , , << , stdin );
}
~io()
{
fwrite( obuf , , t - obuf , stdout );
}
inline int read()
{
register int u = ;
while( * s < ) s++;
while( * s > )
u = u * + * s++ - ;
return u;
}
template < class T >
inline void print( T u , int v )
{
print( u );
* t++ = v;
}
template< class T >
inline void print( register T u )
{
static int * q = a;
if( !u ) * t++ = ;
else
{
if( u < )
* t++ = , u *= -;
while( u ) * q++ = u % + , u /= ;
while( q != a )
* t++ = * --q;
}
}
} ip; #define read ip.read
#define print ip.print inline void addedge( int x , int y )
{
linker[x].push_back( y );
linker[y].push_back( x );
} int main()
{
#ifdef OPENSTACK
int size = << ; // 64MB
char *p = (char*)malloc(size) + size;
#if (defined _WIN64) or (defined __unix)
__asm__("movq %0, %%rsp\n" :: "r"(p));
#else
__asm__("movl %0, %%esp\n" :: "r"(p));
#endif
#endif
srand( time( ) );
for( int s = ; s < ; s++ )
{
left_bit[s] = ssssssss[s] = ;
for( register int i = ; i < ; i++ )
if( !( ( s >> i ) & ) )
{
left_bit[s] = i;
break;
}
for( register int i = ; ~i ; i-- )
if( !( ( s >> i ) & ) )
{
ssssssss[s] = - i;
break;
}
}
n = read() , m = read();
for( int i = ; i <= n ; i++ )
for( register int j = wocaonimabis[][i] = ; j <= ; j++ )
wocaonimabis[][] = , wocaonimabis[j][i] = wocaonimabis[j - ][i] * i;
for( int j = ; j <= ; j++ )
for( int s = ; s < ; s++ )
{
int len = ;
for( register int i = left_bit[s] + ; i <= - ssssssss[s] ; i++ )
if( ( s >> i ) & ) len++;
else f[j][s] += wocaonimabis[j][ len ] , len = ;
if( len ) f[j][s] += wocaonimabis[j][ len ];
}
for( register int i = ; i <= n ; i++ ) a[i] = read();
for( register int i = ; i < n ; i++ ) addedge( read() , read() );
dfs1( ) , dfs2( , );
for( int i = ; i <= min( n , Q ) ; i++ )
{
int pos;
while( vis[ pos = rand() * rand() % n + ] );
vis[ pos ] = , tag[i] = pos , caocoacao[ tag[i] ] = i;
}
for( int i = ; i <= min( n , Q ) ; i++ )
{
int cur = tag[i];
ans.clear();
do
{
ans |= a[ cur ];
if( cur != tag[i] && caocoacao[cur] )
{
BIT[i][ caocoacao[ cur ] ] |= ans;
if( !up[ tag[i] ] )
up[ tag[i] ] = cur;
}
cur = fa[ cur ];
}
while( cur );
}
for( int i = ; i <= m ; i++ )
{
int cnt = read();
ans.clear();
for( int j = ; j <= cnt ; j++ )
{
int x = read() ^ lastans , y = read() ^ lastans , z = lca( x , y );
ans |= a[z];
while( !caocoacao[x] && x != z )
{
ans |= a[x];
x = fa[x];
}
int now = x;
while( gandan [ up[x] ] > gandan [z] ) x = up[x];
ans |= BIT[ caocoacao[ now ] ][ caocoacao[x] ];
while( x != z )
{
ans |= a[x];
x = fa[x];
}
while( !caocoacao[y] && y != z )
{
ans |= a[y];
y = fa[y];
}
now = y;
while( gandan [ up[y] ] > gandan [z] ) y = up[y];
ans |= BIT[ caocoacao[ now ] ][ caocoacao[y] ];
while( y != z )
{
ans |= a[y];
y = fa[y];
}
}
print( lastans = ans.find( read() ) , '\n' );
}
#ifdef OPENSTACK
exit();
#else
return ;
#endif
return ;
}