頹coding

題目連結： http://tioj.infor.org/contests/55/problems/1993 背包問題，但是需要用bitset壓常數。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; bitset< 100005 > ok; int main (){jizz int t;cin >> t; while(t--){ ok. reset (); int n,h;cin >> n >> h; ok[0] = 1; for(int i = 0 ; i < n ; i++){ int a,b,c;cin >> a >> b >> c; ok = (ok << a)|(ok << b)|(ok << c); } int ans = 0; for(int i = 0 ; i <= h ; i++)if(ok[i])ans = i; if(!ans)cout <<"no solution" << endl; ...

題目連結： http://tioj.infor.org/problems/1991 不難發現答案可以利用前綴和來維護，既然是二維的那就用前綴和的前綴和來維護。 一個記放橫的答案，另一個記放直的答案。 因為陣列難先開好，所以把座標Hash掉。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; int r,c; bitset< 1000006 > box; int a[ 1000006 ],b[ 1000006 ]; inline int h (int x,int y){ if(x < 1 || x > r || y < 1 || y > c)return 1000005; return c*(x-1)+y; } int main (){jizz cin >> r >> c; for(int i = 1; i <= r; i++){ for(int j = 1; j <= c; j++){ bool o;cin >> o; box[ h (i,j)] = o; } } for(int i = 1; i <= r; i++){ for(int j =...

題目連結： http://tioj.infor.org/problems/1994 裸裸的遞迴下去，判斷朝向哪一邊即可～ 我的code挺暴力的>< # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; int a[ 2050 ][ 2050 ]; void make (int x,int y,int l,int r,int sta){ if(r - l == 3){ if(sta == 1)a[x][y] = l,a[x+1][y] = l+1,a[x+1][y+1] = r-1,a[x][y+1] = r; if(sta == 2)a[x][y] = l,a[x+1][y] = r,a[x+1][y+1] = r-1,a[x][y+1] = l+1; if(sta == 3)a[x][y] = r-1,a[x+1][y] = r,a[x+1][y+1] = l,a[x][y+1] = l+1; if(sta == 4)a[x][y] = r-1,a[x+1][y] = l+1,a[x+1][y+1] = l,a[x][y+1] = r; return; } int t = (r-l+1)/4; int p = sqrt(r-l+1)/2; if(sta ...

題目連結： http://tioj.infor.org/problems/1388 dp[l][r]代表區間(l,r)的最佳解，而(r-l+1)的奇偶將判斷他們是要用加的還是減的。 # include < iostream > # define lld long long # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; lld dp[ 105 ][ 105 ]; int main (){jizz int n; while(cin >> n){ fill(&dp[0][0],&dp[105][105],0); for(int i = 1; i <= n ; i++)cin >> dp[i][i]; for(int j = 2; j <= n ; j++){ for(int i = j-1 ; i >= 1 ; i--){ for(int k = i ; k < j ; k++){ dp[i][j] = max(dp[i][j],((j-i+1)&1 ? dp[i][k]*dp[k+1][j] : dp[i][k]+dp[k+1][j])); } } } cout << dp[1][n] << endl; } return 0; }

題目連結： http://tioj.infor.org/problems/1699 莫隊算法的經典題，區間眾數。 對數值離散化之後，開陣列紀錄數字 x 出現了幾次，以及有幾種數字出現了 y 次。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; struct Query{ int l,r,k,id,lid; bool operator < (const Query & x) const{ return lid == x.lid ? r < x.r : lid < x.lid; } }q[ 1000005 ]; bitset< 1000005 > as; int n,m,t,a[ 50005 ],ans; int num[ 50005 ],cnt[ 50005 ]; void add (int x){ cnt[num[x]]--; num[x]++; cnt[num[x]]++; ans = max(ans,num[x]); } void sub (int x){ cnt[num[x]]--; num[x]--; cnt[num[x]]++; if(!cnt[ans])ans--; } void MO (){ sort(q,q+...

題目連結： http://tioj.infor.org/problems/1279 從數字最大的那格一路選下來會是最佳解。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; int gx[] = {0,1,0,-1},gy[] = {1,0,-1,0}; struct Ken{ int w,x,y; bool operator<(const Ken &_)const{ return _.w > w; } }; priority_queue<Ken> pq; bitset< 1005 > ok[ 1005 ]; int a[ 1005 ][ 1005 ]; int main (){jizz int n,m;cin >> n >> m; lld ans = 0; for(int i = 0 ; i < n ; i++){ for(int j = 0 ;j < m ; j++){ cin >> a[i][j]; pq. push ({a[i][j],i,j}); ans += a[i][j]; } } while(...

題目連結： http://tioj.infor.org/problems/1546 不難發現做什麼操作的順序並不重要，一定有一位必輸，因此只要把可以做幾次操作算出來再mod N即可。 因為a xor b xor b 會等於 a ，所以可以觀察出[a][b]項 其實就是 [0][0] xor [a][0] xor [0][b]。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; int u[ 10004 ],l[ 10004 ]; lld ans,p,q; inline lld count (int x){ if(x >= q)return q-p+1; if(x < p)return 0; return x-p+1; } inline int num (int x,int y){ if(x == 0)return u[y]; if(y == 0)return l[x]; return u[0]^l[x]^u[y]; } int main (){jizz int n,m;cin >> n >> m >> p >> q; ans = m*m-2*m+1; for(int i = 0 ; i < m ; i++)cin >> u[i]...