A. Bracket Expression
直接按题意模拟即可。
时间复杂度$O(n)$。
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int,int>pi;
const int Maxn=55;
char s[Maxn];
int ls;
LL sta[Maxn];
int top=0;
int main(){
freopen("bracket-expression.in","r",stdin);
freopen("bracket-expression.out","w",stdout);
fgets(s,sizeof s,stdin);
for(int i=0;(s[i]=='(')||(s[i]==')');i++){//-1,-2
if(s[i]=='(')sta[top++]=-1;
else{
LL cur=1;
while(top&&sta[top-1]!=-1){
cur=cur*sta[top-1];
top--;
}
sta[top-1]=cur+1;
}
}
LL ret=1;
while(top)ret=1LL*ret*sta[top-1],top--;
printf("%lld
",ret);
return 0;
}
B. Checkers
暴力搜索所有对战情况，然后模拟。
时间复杂度$O(2^nk)$。
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int,int>pi;
int n,k;
string s[22];
int ans=0;
int jud(vector<int>&V,string &s){
for(int i=V.size()-1,j=s.size()-1;i>=0&&j>=0;i--,j--){
if(V[i]==(s[j]=='W'))continue;
if(V[i])return 0;
else return 1;
}
return 1;
}
void dfs(int cur,int op,int win,vector<int>V){
if(cur>=k){
ans=max(ans,win);
return;
}
for(int i=1;i+cur<=k&&i<=2;i++){
string tmp=s[op];
vector<int>nxt=V;
int tmpwin=win;
for(int j=0;j<i;j++){
int res=jud(nxt,s[op]);
nxt.push_back(res);
if(res)tmpwin++;
s[op].push_back(res?'B':'W');//res==1:w
}
dfs(cur+i,(op+1)%n,tmpwin,nxt);
s[op]=tmp;
}
}
int main(){
freopen("checkers.in","r",stdin);
freopen("checkers.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)cin>>s[i];
vector<int>V;
dfs(0,0,0,V);
printf("%d
",ans);
return 0;
}
C. Convex and Compact
枚举起点，设$f[i][j][k]$表示当前凸包转到了$i$点，凸包上和内部有$j$个点，凸包上有$k$个点时凸包的最小周长，然后DP即可。
时间复杂度$O(n^4k)$。
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
typedef pair < int , int > pii ;
#define clr( a , x ) memset ( a , x , sizeof a )
const int MAXN = 65 ;
const double INF = 1e60 ;
const double eps = 1e-8 ;
const double pi = acos ( -1.0 ) ;
int dcmp ( double x ) {
return ( x > eps ) - ( x < -eps ) ;
}
struct Point {
int x , y ;
Point () {}
Point ( int x , int y ) : x ( x ) , y ( y ) {}
bool operator < ( const Point& a ) const {
return x != a.x ? x < a.x : y < a.y ;
}
Point operator + ( const Point& a ) const {
return Point ( x + a.x , y + a.y ) ;
}
Point operator - ( const Point& a ) const {
return Point ( x - a.x , y - a.y ) ;
}
int operator * ( const Point& a ) const {
return x * a.y - y * a.x ;
}
double angle () {
return atan2 ( y , x ) ;
}
double len () {
return sqrt ( 0.0 + x * x + y * y ) ;
}
} ;
struct Node {
double r ;
int idx ;
bool operator < ( const Node& a ) const {
return r < a.r ;
}
} ;
struct Pre {
int x , y , z ;
Pre () {}
Pre ( int x , int y , int z ) : x ( x ) , y ( y ) , z ( z ) {}
} ;
Node a[MAXN] ;
Point p[MAXN] ;
int n , K ;
int in[MAXN][MAXN] ;
Pre pre[MAXN][MAXN][17] ;
double len2[MAXN][MAXN] ;
double dp[MAXN][MAXN][17] ;
double ans ;
int S[MAXN] , top ;
int vis[MAXN] ;
int id[MAXN] ;
int cmp ( const int&a , const int& b ) {
return p[a].x != p[b].x ? p[a].x < p[b].x : p[a].y < p[b].y ;
}
bool PointInTri ( int i , int j , int k , int l ) {
LL a = ( p[i] - p[l] ) * ( p[j] - p[l] ) ;
LL b = ( p[j] - p[l] ) * ( p[k] - p[l] ) ;
LL c = ( p[k] - p[l] ) * ( p[i] - p[l] ) ;
return a * b > 0 && b * c > 0 && c * a > 0 ;
}
void insert ( int x , int y , int z ) {
Pre t = pre[x][y][z] ;
if ( t.x ) insert ( t.x , t.y , t.z ) ;
S[top ++] = a[x].idx ;
}
void calc ( int m ) {
for ( int i = 0 ; i <= m ; ++ i ) {
for ( int j = 0 ; j <= m + 1 ; ++ j ) {
for ( int k = 0 ; k <= K ; ++ k ) {
dp[i][j][k] = INF ;
pre[i][j][k] = Pre ( 0 , 0 , 0 ) ;
}
}
for ( int j = 0 ; j <= m ; ++ j ) {
len2[i][j] = ( p[a[i].idx] - p[a[j].idx] ).len () ;
}
}
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = i + 1 ; j <= m ; ++ j ) {
in[i][j] = 3 ;
for ( int l = 1 ; l <= m ; ++ l ) if ( l != i && l != j ) {
if ( PointInTri ( a[0].idx , a[i].idx , a[j].idx , a[l].idx ) ) {
in[i][j] ++ ;
}
}
}
}
for ( int i = 1 ; i <= m ; ++ i ) {
dp[i][2][2] = len2[0][i] * 2 ;
pre[i][2][2] = Pre ( 0 , 0 , 0 ) ;
for ( int j = 2 ; j <= m ; ++ j ) {
for ( int k = 3 ; k <= min ( i + 1 , K ) ; ++ k ) {
for ( int l = 1 ; l < i ; ++ l ) if ( dp[l][j][k - 1] < 1e50 ) {
int num = j + in[l][i] - 2 ;
double tmp = dp[l][j][k - 1] - len2[0][l] + len2[0][i] + len2[i][l] ;
if ( dp[i][num][k] > tmp ) {
dp[i][num][k] = tmp ;
//printf ( "%d %d %d %.5f
" , i , num , k , dp[i][num][k] ) ;
pre[i][num][k] = Pre ( l , j , k - 1 ) ;
}
}
}
}
}
int x = -1 , y , z ;
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = K ; j <= m + 1 ; ++ j ) {
for ( int k = 3 ; k <= K ; ++ k ) if ( dp[i][j][k] < 1e50 ) {
//printf ( "dp[%d][%d][%d] = %.5f
" , i , j , k , dp[i][j][k] ) ;
if ( dcmp ( dp[i][j][k] - ans ) < 0 ) {
ans = dp[i][j][k] ;
x = i ;
y = j ;
z = k ;
}
}
}
}
if ( ~x ) {
top = 0 ;
insert ( x , y , z ) ;
S[top ++] = a[0].idx ;
}
}
int check ( int x ) {
LL f = ( p[x] - p[S[0]] ) * ( p[x] - p[S[1]] ) ;
for ( int i = 0 ; i < top ; ++ i ) {
LL ff = ( p[x] - p[S[i]] ) * ( p[x] - p[S[( i + 1 ) % top]] ) ;
if ( f * ff < 0 ) return 0 ;
}
return 1 ;
}
void solve () {
ans = INF ;
for ( int i = 1 ; i <= n ; ++ i ) {
scanf ( "%d%d" , &p[i].x , &p[i].y ) ;
}
if ( K == 1 ) {
printf ( "%d
" , 0 ) ;
printf ( "%d
" , 1 ) ;
return ;
}
if ( K == 2 ) {
int x , y ;
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = i + 1 ; j <= n ; ++ j ) {
double tmp = ( p[i] - p[j] ).len () ;
if ( tmp < ans ) {
ans = tmp ;
x = i ;
y = j ;
}
}
}
printf ( "%.8f
" , ans ) ;
printf ( "%d %d
" , x , y ) ;
return ;
}
for ( int i = 1 ; i <= n ; ++ i ) {
id[i] = i ;
}
sort ( id + 1 , id + n + 1 , cmp ) ;
a[0].r = -INF ;
for ( int i = 1 ; i <= n ; ++ i ) {
int m = 0 ;
for ( int j = i + 1 ; j <= n ; ++ j ) {
++ m ;
a[m].idx = id[j] ;
a[m].r = ( p[id[j]] - p[id[i]] ).angle () ;
//if ( dcmp ( a[j].r ) < 0 ) a[j].r = 2 * pi + a[j].r ;
}
a[0].idx = id[i] ;
sort ( a + 1 , a + m + 1 ) ;
if ( m + 1 >= K ) calc ( m ) ;
}
printf ( "%.8f
" , ans ) ;
int flag = 0 ;
clr ( vis , 0 ) ;
for ( int i = 0 ; i < top ; ++ i ) {
if ( flag ) printf ( " " ) ;
flag = 1 ;
printf ( "%d" , S[i] ) ;
vis[S[i]] = 1 ;
}
for ( int i = top + 1 ; i <= K ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) if ( !vis[j] ) {
if ( check ( j ) ) {
printf ( " %d" , j ) ;
vis[j] = 1 ;
break ;
}
}
}
puts ( "" ) ;
}
int main () {
freopen ( "convexset.in" , "r" , stdin ) ;
freopen ( "convexset.out" , "w" , stdout ) ;
while ( ~scanf ( "%d%d" , &n , &K ) ) solve () ;
return 0 ;
}
D. Forbidden Words
留坑。
E. Four Prime Numbers
设$f[i]$表示用两个质数能拼出$i$的方案数，可以通过暴力枚举两个质数求出，则$ans=sum f[i]f[n-i]$。
时间复杂度$O(frac{n^2}{ln^2n})$。
#include<cstdio>
const int N=100010;
int n,i,j,tot,v[N],p[N],f[N];long long ans;
int main(){
freopen("fourprimes.in","r",stdin);
freopen("fourprimes.out","w",stdout);
scanf("%d",&n);
for(i=2;i<=n;i++){
if(!v[i])p[tot++]=i;
for(j=0;j<tot;j++){
if(i*p[j]>n)break;
v[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
for(i=0;i<tot;i++){
if(p[i]+p[i]<=n)f[p[i]+p[i]]++;
for(j=0;j<i;j++){
if(p[i]+p[j]>n)break;
f[p[i]+p[j]]+=2;
}
}
for(i=1;i<=n;i++)ans+=1LL*f[i]*f[n-i];
printf("%lld",ans);
return 0;
}
F. Set Intersection
随机化找出规律：$ans=lfloorfrac{LM}{N} floor$。
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int,int>pi;
int LIM=1000;
int a[1000020],b[1000020];
int n,l,m;
int c[1000020],ans[1000020];
int main(){
freopen("intset.in","r",stdin);
freopen("intset.out","w",stdout);
while(scanf("%d%d%d",&n,&l,&m)!=EOF){
long long now=1LL*m*l/n;
printf("%lld",now);
/* for(int i=0;i<n;i++)b[i]=i;
for(int i=0;i<LIM;i++){
random_shuffle(b,b+n);
int cur=0;
for(int j=0;j<m;j++){
if(b[j]<l)cur++;
}
ans[cur]++;
}
for(int i=n-1;i>=0;i--)ans[i]+=ans[i+1];
int rep=0;
for(int i=n;i>=0;i--){
if(ans[i]>=LIM/2){
rep=i;
break;
}
}
printf("%d
",rep);*/
}
return 0;
}
G. Medals
将第$x$名的费用设置为$1001^{10-x}$，那么答案就是二分图最大权匹配，费用流求解即可，需要用__int128存储。
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef __int128 LL;
typedef pair<int,int>pi;
const int Maxn=2020,Maxe=200020;
LL Inf=1LL<<60;
LL pw[15];
int ne;
int n,s,t;
vector<int>G[Maxn];
struct E{
int v,c;
LL w;
E(){}
E(int v,int c,LL w):v(v),c(c),w(w){}
}e[Maxe];
void add(int u,int v,int c,LL w){
e[ne]=E(v,c,w);
G[u].push_back(ne++);
e[ne]=E(u,0,-w);
G[v].push_back(ne++);
}
int pre[Maxn],pe[Maxn],inq[Maxn];
LL d[Maxn];
bool spfa(){
for(int i=0;i<=t;i++)d[i]=Inf,inq[i]=0;
d[s]=0;
queue<int>q;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<G[u].size();i++){
int id=G[u][i];
int v=e[id].v;
LL w=e[id].w;
int c=e[id].c;
if(!c)continue;
if(d[v]>d[u]+w){
pre[v]=u;
pe[v]=id;
d[v]=d[u]+w;
if(!inq[v]){q.push(v);inq[v]=1;}
}
}
inq[u]=0;
}
return d[t]<0;
}
int rep[100];
int cho[Maxn];
void costflow(){
LL ans=0;
while(spfa()){
ans-=d[t];
for(int i=t;i!=s;i=pre[i]){
e[pe[i]].c--;
e[pe[i]^1].c++;
}
}
for(int i=0;i<10;i++)rep[10-i]=ans%1001,ans/=1001;
for(int i=1;i<=10;i++)printf("%d%c",rep[i],i==10?'
':' ');
for(int i=1;i<=n;i++){
cho[i]=0;
for(int j=0;j<G[i].size();j++){
int id=G[i][j];
if(e[id].v!=s&&(!e[id].c)){
cho[i]=e[id].v-n;
}
}
}
for(int i=1;i<=n;i++)printf("%d%c",cho[i],i==n?'
':' ');
}
int main(){
freopen("medals.in","r",stdin);
freopen("medals.out","w",stdout);
pw[0]=1;
Inf*=Inf;
for(int i=1;i<=11;i++)pw[i]=pw[i-1]*1001;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int k;scanf("%d",&k);
for(int j=0;j<k;j++){
int id,rk;
scanf("%d%d",&id,&rk);
add(i,id+n,1,-pw[10-rk]);
}
add(s,i,1,0);
}
s=0;t=n+1000+1;
for(int i=n+1;i<t;i++)add(i,t,1,0);
costflow();
return 0;
}
H. Reachability
对于每个询问，压位记忆化搜索即可。
时间复杂度$O(frac{qn^3}{64})$。
#include<cstdio>
#include<bitset>
using namespace std;
typedef unsigned int U;
const int N=405;
typedef bitset<N>DS;
int n,m,i,A,B;bool g[N][N],v[N];
U pa[N],pb[N];
DS f[N];
void dfs(int x){
if(v[x])return;
v[x]=1;
for(int i=1;i<=n;i++)if(g[x][i]){
dfs(i);
f[x]|=f[i];
}
}
inline void vio(){
int i,j;
for(i=1;i<=n;i++){
v[i]=0,f[i].reset();
f[i][i]=1;
}
for(i=1;i<=n;i++)if(!v[i])dfs(i);
U ret=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j]==1&&i!=j){
// printf("%d->%d
",i,j);
ret+=pa[i-1]*pb[j-1];
}
printf("%u
",ret);
}
int main(){
freopen("reachability.in","r",stdin);
freopen("reachability.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&A,&B);
for(pa[0]=i=1;i<=n;i++)pa[i]=pa[i-1]*A;
for(pb[0]=i=1;i<=n;i++)pb[i]=pb[i-1]*B;
for(i=1;i<=m;i++){
char op1[5],op2[5];
int x,k,y;
scanf("%s%s%d%d",op1,op2,&x,&k);
if(op2[0]=='o'){
while(k--)scanf("%d",&y),g[x][y]^=1;
}else{
while(k--)scanf("%d",&y),g[y][x]^=1;
}
vio();
}
return 0;
}
I. Revolving Lasers
留坑。
J. Snakes on the Stone
从蛇头开始走，每次碰到交点就往上走即可，这样一定可以保证不打结。
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
typedef pair < int , int > pii ;
#define clr( a , x ) memset ( a , x , sizeof a )
const int MAXN = 30 ;
int a[MAXN][MAXN] , n , m[3] ;
int vis[MAXN][MAXN] ;
int x[3][MAXN * MAXN] , y[3][MAXN * MAXN] ;
void solve () {
clr ( a , 0 ) ;
clr ( vis , 0 ) ;
for ( int i = 0 ; i < n ; ++ i ) {
scanf ( "%d" , &m[i] ) ;
for ( int j = 1 ; j <= m[i] ; ++ j ) {
scanf ( "%d%d" , &x[i][j] , &y[i][j] ) ;
vis[x[i][j]][y[i][j]] ++ ;
}
}
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 1 ; j <= m[i] ; ++ j ) {
int r = x[i][j] , c = y[i][j] ;
if ( vis[r][c] == 2 ) {
if ( !a[r][c] ) {
++ a[r][c] ;
putchar ( '-' ) ;
} else {
putchar ( '+' ) ;
}
}
}
puts ( "" ) ;
}
}
int main () {
freopen ( "snakes2.in" , "r" , stdin ) ;
freopen ( "snakes2.out" , "w" , stdout ) ;
while ( ~scanf ( "%d" , &n ) ) solve () ;
return 0 ;
}
K. Dependent Subsets
选出的这些向量的秩只能是$1$或$2$，枚举一个基向量，用它去对其它向量进行消元，约分之后排序，首先被消完的向量都可以选入，然后再选若干个约分后完全相等的向量即可。
时间复杂度$O(n^2d)$。
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int,int>pi;
const int Maxn=1020;
int n,d;
vector<int> a[Maxn];
vector<int> b[Maxn];
int id[Maxn];
int use[Maxn];
int st[Maxn];
bool cmp(int t1,int t2){
return b[t1]<b[t2];
}
int xiao(vector<int>&x){//return first nonzero loc
int fst=x.size();
for(int i=0;i<x.size();i++){
if(x[i]!=0){fst=i;break;}
}
if(fst>=x.size())return fst;
int gc=abs(x[fst]);
for(int i=fst+1;i<x.size();i++){
if(x[i]!=0){
gc=__gcd(abs(x[i]),gc);
}
}
int tmp=x[fst]<0?(-gc):gc;
for(int i=fst;i<x.size();i++){
if(x[i]!=0)x[i]=x[i]/tmp;
}
return fst;
}
vector<int> dec(vector<int>&x,vector<int>&y,int st1,int st2){
if(!y[st1])return y;
vector<int>ret=x;
int lcm=x[st1]*abs(y[st1])/__gcd(x[st1],abs(y[st1]));
int be1=lcm/x[st1],be2=lcm/y[st1];
for(int i=0;i<x.size();i++)ret[i]=x[i]*be1-y[i]*be2;
return ret;
}
void pt(vector<int>&x){
for(int i=0;i<x.size();i++)printf("%d ",x[i]);puts("");
}
bool iszero(vector<int>&x){
for(int i=0;i<x.size();i++)if(x[i])return 0;
return 1;
}
int main(){
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++){
for(int j=0;j<d;j++){
int x;scanf("%d",&x);
a[i].push_back(x);
}
}
for(int i=1;i<=n;i++)st[i]=xiao(a[i]);
vector<int>rep;
for(int i=1;i<=n;i++){
int cnt=0;
for(int j=i+1;j<=n;j++){
b[cnt]=dec(a[i],a[j],st[i],st[j]);
xiao(b[cnt]);
use[cnt]=cnt;
id[cnt]=j;
cnt++;
}
sort(use,use+cnt,cmp);
int sel=-1,sr;
int now=0;
vector<int>tmp;
tmp.push_back(i);
for(;now<cnt&&iszero(b[use[now]]);now++)tmp.push_back(id[use[now]]);
int tmpans=0;
for(int j=now,k;j<cnt;j=k){
for(k=j+1;k<cnt&&b[use[k]]==b[use[j]];k++);
if((k-j)>tmpans){
sel=j;
sr=k;
tmpans=k-j;
}
}
if(sel>=0){
for(int j=sel;j<sr;j++)tmp.push_back(id[use[j]]);
}
if(tmp.size()>rep.size())swap(tmp,rep);
}
printf("%d
",(int)rep.size());
for(int i=0;i<rep.size();i++)printf("%d%c",rep[i],i==rep.size()-1?'
':' ');
return 0;
}