A artwork
离线并查集维护，然后逐步撤销。撤销后若为白点，判断上下左右不同连通块的数目k，ans[op] -= （k-1） 。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll ;
int par[1<<20] ;
int ma[1010][1010] ;
struct node{int x1 , y1 , x2 , y2 ;
}operation[100020];
int ans[100020] ;
int find1(int x){if(x == par[x]) return x ;return par[x] = find1(par[x]) ;
}
int unite(int x , int y){int a = find1(x) ; int b = find1(y) ;if(a == b) return 0 ;if(a > b) swap(a , b) ;par[b] = a ;return 1 ;
}
int n , m , op ;
int dx[4] = {-1 , 0 , 1 , 0} ;
int dy[4] = {0 , -1 , 0 , 1} ;
int work(int x , int y , int value){if(ma[x][y] != value) return 0 ;ma[x][y] = 0 ;int ans = 1 ;for(int i = 0 ; i <= 3 ; i ++ ){int xn = x + dx[i] , yn = y + dy[i] ;if(xn <= 0 || xn > m || yn <= 0 || yn > n || ma[xn][yn] ) continue ;ans -= unite(x<<10|y , xn<<10|yn) ;}return ans ;
}
int init(){int ans = 0 ;for(int i = 1 ; i <= m ; i ++ ){for(int j = 1 ; j <= n ; j ++ ){ans += work(i , j , 0) ;}}return ans ;
}
int main(){int a , b , c , d;while( ~ scanf("%d %d %d" , &n , &m , &op)){memset(ma , 0 , sizeof(ma)) ;for(int i = 1 ; i <= op ; i ++ ){node & te = operation[i] ;scanf("%d %d %d %d" , &te.y1 , &te.x1 , &te.y2 , &te.x2) ;if(te.y1 > te.y2) swap(te.y1 , te.y2) ;if(te.x1 > te.x2) swap(te.x1 , te.x2) ;}for(int i = 0 ; i < 1<<20 ; i ++ ) par[i] = i ;for(int i = op ; i >= 1 ; i -- ){node & te = operation[i] ;if(te.x1 == te.x2) for(int j = te.y1 ; j <= te.y2 ; j ++ ){ ma[te.x1][j] = i ; }else for(int j = te.x1 ; j <= te.x2 ; j ++ ) {ma[j][te.y1] = i ;}}/*for(int i = 1 ; i <= m ; i ++ ){for(int j = 1 ; j <= n ; j ++ )cout << ma[i][j] << " " ;cout << endl ;}*/ans[op + 1] = init() ;for(int i = op ; i >= 2 ; i -- ){node & te = operation[i] ;ans[i] = ans[i + 1] ;if(te.x1 == te.x2){for(int j = te.y1 ; j <= te.y2 ; j ++ )ans[i] += work(te.x1 , j , i) ;}else{for(int j = te.x1 ; j <= te.x2 ; j ++ )ans[i] += work(j , te.y1 , i) ;}}for(int i = 2 ; i <= op + 1; i ++ ) printf("%d\n" , ans[i]) ;}return 0 ;
}
#include <bits/stdc++.h>
using namespace std;
const int maxn = 310;
const int inf = 0x3f3f3f3f;
const int N = 1001 ;
int ma[1505][1505] ;
int par[1505][1505] ;
struct point { int x , y ;};
struct node{int x1 , y1 , x2 , y2 ;node(){}node(int a , int b , int c , int d) : x1(a) , y1(b) , x2(c) , y2(d){}
}operation[10050];
int n , m , q ;
int ans[10050] ;
int find1(int i , int j ){if(par[i][j] == ( i - 1 ) * m + j ) return par[i][j] ;return par[i][j] = find1( par[i][j] / m + 1 , par[i][j] % m ) ;
}
int dx[4] = {0 , -1 , 0 , 1} ;
int dy[4] = {-1 , 0 , 1 , 0} ;
int init(){set<int> ppp ; ppp.clear() ;memset(par, 0 , sizeof(par)) ;for(int i = 1 ; i <= n ; i ++ ){for(int j = 1 ; j <= m ; j ++ ){if(ma[i][j]) continue ;for(int k = 0 ; k <= 3 ; k ++){if(par[ i + dx[k] ][ j + dy[k] ]){ par[i][j] = par[ i + dx[k] ][ j + dy[k] ] ; break ; }}if( ! par[i][j] ) par[i][j] = (i - 1) * m + j ;ppp.insert(par[i][j]) ;}}return ppp.size() ;
}
void unite(int x1 , int y1 , int x2 , int y2){int a = find1(x1 , y1) , b = find1(x2 , y2) ;if(a == b) return ;if(a!= 0 && b!=0){a = min(a , b) ;}else{a = max(a , b) ;}par[x1][y1] = a ;par[x2][y2] = a ;
}
/*
4 4 4
2 1 2 4
1 2 4 2
3 4 3 4
4 3 4 3
*/
int main()
{while( ~ scanf("%d %d %d" , &n , &m , &q)){memset(ma , 0 , sizeof(ma)) ;memset(ans , 0 , sizeof( ans )) ;int pos = 0 ;int a , b , c , d ;for(int i = 0 ; i < q ; i ++ ){scanf("%d %d %d %d" , &a , &b , &c , &d) ;if(a == c){int e = min(b , d) ; int f = max(b , d) ;operation[i] = node( a , e , a , f ) ;for(int j = e ; j <= f ; j ++) {ma[a][j] ++ ;}}else if(b == d){int e = min(a , c) ; int f = max(a , c ) ;operation[i] = node( e , b , f , b ) ;for(int j = e ; j <= f ; j ++ ){ma[j][b] ++ ;}}}ans[q] = init() ;node temp ;set<int> pq ;for(int op = q - 1 ; op >= 0 ; op -- ){temp = operation[op] ;ans[op] = ans[op + 1] ;a = temp.x1 , b = temp.y1 , c = temp.x2 , d = temp.y2 ;if( a == c ){for(int i = b ; i <= d ; i ++ ){ma[a][i] -- ;if(! ma[a][i]){pq.clear() ;for(int k = 0 ; k <= 3 ; k ++ ){if( a + dx[k] > n || a + dx[k] <= 0 || i + dy[k] > m || i + dy[k] <= 0 ) continue ;if(! par[ a + dx[k] ][ i + dy[k] ] ) continue ;pq.insert( find1( a + dx[k] , i + dy[k] ) ) ;}ans[op] = ans[op] - pq.size() + 1 ;for(int k = 0 ; k <= 3 ; k ++ ){if( a + dx[k] > n || a + dx[k] <= 0 || i + dy[k] > m || i + dy[k] <= 0 || !par[ a + dx[k] ][ i + dy[k] ] ) continue ;unite( a , i , a + dx[k] , i + dy[k] ) ;/*if( op == 3 ){ cout << ans[op] << " " << pq.size() << " >>>>" << endl ; cout << par[4][4] << " ??" << endl ;for(int i = 1 ; i <= n ; i ++ ){for(int j = 1 ; j <= m ; j ++ )cout << par[i][j] << " " ;cout << endl ;}}*/}if(par[a][i] == 0) par[a][i] = (a - 1 )* m + i ;}}}else if( b == d ){for(int i = a ; i <= c ; i ++ ){ma[i][b] -- ;if( ! ma[i][b] ){pq.clear() ;for(int k = 0 ; k <= 3 ; k ++ ){if( i + dx[k] > n || i + dx[k] <= 0 || b + dy[k] > m || b + dy[k] <= 0 ) continue ;if(! par[ i + dx[k] ][ b + dy[k] ] ) continue ;pq.insert( find1( i + dx[k] , b + dy[k] ) ) ;}ans[op] = ans[op] - pq.size() + 1 ;for(int k = 0 ; k <= 3 ; k ++ ){if( i + dx[k] > n || i + dx[k] <= 0 || b + dy[k] > m || b + dy[k] <= 0 || !par[ i + dx[k] ][ b + dy[k] ]) continue ;unite( i , b , i + dx[k] , b + dy[k] ) ;}if(par[i][b] == 0) par[i][b] = ( i - 1 )* m + b ;}}}}for(int i = 1 ; i <= q ; i ++ )printf("%d\n" , ans[i]) ;}return 0;
}
B. Bless You Autocorrect!
unsolved
C. Card Hand Sorting
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;template <class It> int lisLength(It begin, It end) {typedef typename iterator_traits<It>::value_type T;T inf = 1<<30;vector<T> best(end-begin,inf);for (It i = begin; i != end; ++i)*lower_bound(best.begin(),best.end(),*i) = *i;return lower_bound(best.begin(),best.end(),inf)-best.begin();
}int main() {int n;cin >> n;vector< pair<int, int> > hand(n, pair<int, int>(0,0) );map<char, int> rank;rank['T'] = 10;rank['J'] = 11;rank['Q'] = 12;rank['K'] = 13;rank['A'] = 14;map<char, int> suit;suit['s'] = 0;suit['h'] = 1;suit['d'] = 2;suit['c'] = 3;char s[3];for (int i = 0; i < n; ++i) {cin >> s;if (rank.count(s[0]))hand[i].first = rank[s[0]];elsehand[i].first = s[0]-'0';hand[i].second = suit[s[1]];}int suit_order[] = {0, 1, 2, 3};int res = 0;for (int order = 0; order < 4*3*2; ++order) {for (int direction = 0; direction < 16; ++direction) {vector<int> value(n, 0);for (int i = 0; i < n; ++i) {value[i] = suit_order[hand[i].second]*100 +hand[i].first * (1 - 2*!!(direction&(1<<hand[i].second)));//cout << value[i] << " ";}//cout << endl;/*if (lisLength(value.begin(), value.end()) > res) {for (int i = 0; i < n; ++i) {cout << value[i] << " ";}cout << endl;}*/res = max(res, lisLength(value.begin(), value.end()));}next_permutation(suit_order, suit_order+4);}cout << n-res << endl;
}
D. Daydreaming Stockbroker
简单链表模拟
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1000
typedef long long ll ;
ll sa[500] ;
ll check(ll total , ll a){ll ans ;ans = total / a ;if(ans >= 100000) return 100000 ;return ans ;
}
int main() {int n ;while( ~ scanf("%d" , &n)){for(int i = 0 ; i < n ; i ++ ){scanf("%lld" , &sa[i]) ;}bool flag= 0 ;ll total = 100 ;ll pre = 0 ;ll gu = 0 ;for(int i = 1 ; i < n ; i ++ ){if( !flag ){if(sa[i] >= sa[i-1]) {flag = 1 ; gu = check(total , sa[i-1]) ; total -= sa[i-1] * gu ; }else{}}else if(flag){if(sa[i] >= sa[i-1]){}else{total += gu * sa[i-1] ;flag = 0 ;}}}if(flag){total += gu * sa[n - 1] ;}printf("%lld\n" , total) ;}return 0;
}
E. Exponial
欧拉递推
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;ll n,m,ans;ll euler(ll n){ll res=n,a=n;for(ll i=2;i*i<=a;i++){if(a%i==0){res=res/i*(i-1);while(a%i==0) a/=i;}}if(a>1) res=res/a*(a-1);return res;
}ll fast_mod(ll x,ll n,ll Max)
{ll res=1;while(n>0){if(n & 1)res=(res*x)%Max;x=(x*x)%Max;n >>= 1;}return res;
}ll func(ll n,ll m){if(m==1) return 0;if(n<=5){ll ans=1;for(int i=1;i<=n;i++){ans=fast_mod(i,ans,m);}return ans;}else{ll phi=euler(m);ll z=func(n-1,phi);ans=fast_mod(n,phi+z,m);}return ans;}int main(){while( ~ scanf("%lld %lld" , &n , &m))printf("%lld\n" , func(n , m)) ;return 0;
}
F. Fleecing the Raffle
概率dp
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
ll n , m ;
double dp[100050] ;
/*double solve(double parameter)
{double k = 1 ;for(ll i = n - m + 2 ; i <= n ; i ++ ) k = k * i / (i - 1 + parameter) ;k = k * parameter * m / (n + parameter) ;return k ;
}double trisection_search(double left, double right)
{double midl, midr;while (right-left > 1){midl = (left + right) / 2;midr = (midl + right) / 2;if(solve(midl) >= solve(midr)) right = midr;else left = midl;}return left;
}*/int main(){while( ~ scanf("%lld %lld" , &n , &m)){memset(dp , 0 , sizeof(dp)) ;dp[1] = 1 ;for(ll i = n - m + 2 ; i <= n ; i ++ ) dp[1] = dp[1] * i / ( i - 1 + 1) ;dp[1] = dp[1] * m / (n + 1) ;double ans = dp[1] ;for(ll i = 2 ; i <= n ; i ++ ){dp[i] = dp[i-1] * i / ( i - 1 ) * ( n + i - m ) / (n + i) ;ans = max(ans , dp[i]) ;if(dp[i] <= dp[i-1]) break ;}printf("%.8f\n" , ans ) ;}return 0;
}
G. Game Rank
炉石
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
char a[10005];
int prank(int a){if(a<=25&&a>=21)return 2;if(a<=20&&a>=16)return 3;if(a<=15&&a>=11)return 4;if(a<=10&&a>=1)return 5;if(a<=0)return 1;
}
int main()
{while(~scanf("%s",a)){int ranka=25;int p=0;int star=0;for(int i=0;a[i]!='\0';i++){if(a[i]=='L'){p=0;if(ranka<=25&&ranka>=21)continue;if((ranka==25||ranka==20||ranka<=0)&&!star){continue;}else{if(star)star--;else{ranka++;if(prank(ranka) == 1)star = 0 ;elsestar = prank(ranka)-1;}}}else{p ++ ;if(ranka <= 5)p = 0 ;if(ranka <= 0)continue;else{if(p >= 3)star += 2;elsestar += 1;while(1){if(star > prank(ranka)){star -= prank(ranka);ranka -- ;}elsebreak;}}}}if(ranka<=0)printf("Legend\n");elseprintf("%d\n",ranka);memset(a,'\0',sizeof(a));}return 0;
}J. Jumbled Compass
水题
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std ;
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
int main(){int m , n ;int ans ;while( ~ scanf("%d %d" , &m , &n)){if(m == n) { printf("%d\n" , 0) ; continue ;}int a ;if(n >= m) a = n - m ; else a = n + 360 - m ;int b ;if(m < n)b = m + 360 - n ; else b = m - n ;ans = min(a , b) ;//if(m + ans == n || (m + ans)% 360 == n ) printf("%d\n" , ans) ;if(ans == a) printf("%d\n" ,ans) ;else printf("%d\n" , -ans ) ;}return 0 ;
}