D.Defuse the Bombs（二分答案）
思路：直接二分答案K，判斷能不能在K次操作以內，把所有的數都變成 >= K就行了，最后答案等于K+1
AC代碼：
#include <bits/stdc++.h>
#define int long long
#define showcase cout<<"Case #"<<cas++<<": ";
using namespace std;
int a[100050];
int T,cas = 1;
int n,m;
bool check(int k){
int res = 0;
for(int i = 0 ; i < n ; i ++){
if(k<=a[i]) continue;
res += max((int)0,k-a[i]);
if(res > k ) return false;
}
return res <= k;
}
signed main(){
cin>>T;
while(T--){
cin>>n;
for(int i = 0 ; i < n ; i ++)
cin>>a[i];
int l = 0,r = 1e18;
int res = 0;
while(l <= r){
int mid = (l+r)>>1;
if(check(mid)){
res = max(res,mid);
l = mid+1;
}else{
r = mid-1;
}
}
cout<<"Case #"<<cas++<<": "<<res+1<<endl;
}
}
G.Game of Cards（博弈）
思路：比賽時還是沒有想出來，后來仔細推了一下感覺也不是很難，但是分很多很多種情況，首先可以很容易的發現，答案和 cnt1%3 的值有關，并且和 cnt0%2 的值有關，與cnt3無關，
- 首先考慮 cnt0 == 0 的情況，那就是如下圖所示的情況了，顯然當cnt2 等于0 或者 不等于0 時都是一個關于3的回圈（但是兩者不相同），那就直接按規律輸出就好了，
- 對于cnt0 != 0 的情況，還得特判，如果后面三個都是0，那么只能 0+0 了，也就是每次減少一張 0卡牌 的數量，那么答案和 cnt0 的奇偶性有關，
- 對于cnt0 != 0 且 后面不全為0的情況，還要判斷，cnt2 是 0 還是1，因為對于 cnt2 >= 2 ,那么所有的轉移都是相同的，而當cnt2 == 1 和cnt2 == 0 時，轉移方向雖然是相同的，但是轉移的結果不相同，所以還得區分，（反正就是一堆特判）
- 對于剩下的規則的狀態，就判斷能不能找到一個狀態使得轉移之后還是必勝態了，
AC代碼：
#include <bits/stdc++.h>
#define int long long
using namespace std;
int cas = 1;
int tt1[3] = {0,0,1}; // 2號卡牌數量為0 的勝負情況
int tt2[3] = {0,1,1}; // 2號卡牌數量非0 的勝負情況
void show(int x){
cout<<"Case #"<<cas++<<": ";
if(x) cout<<"Rabbit"<<endl;
else cout<<"Horse"<<endl;
}
signed main(){
int t;
cin>>t;
while(t--){
int cnt0,cnt1,cnt2,cnt3;
cin>>cnt0>>cnt1>>cnt2>>cnt3;
if(cnt1 + cnt2 + cnt3 == 0){
if(cnt0 <= 1)
show(0);
else
show(cnt0%2 == 0);
}else{
int flag1 = cnt0%2;
cnt1 %= 3;
if(cnt0 == 0){ // 沒有0號卡牌的情況，直接按規律輸出
if(cnt2 == 0){ // 沒有2號卡牌的情況，特判
show(tt1[cnt1]);
}else{
show(tt2[cnt1]);
}
}else if(cnt2 == 0){ // 沒有2號卡牌的情況，特判，又因為存在0號卡牌，要異或一下
show(tt1[cnt1]^flag1);
}else if(flag1){ // 如果可以轉移到對手的必勝態，則自己可以獲勝
if(cnt1 == 2 || cnt1 == 0){
show(1);
}else{
show(0);
}
}else{
if(cnt1 == 2 || cnt1 == 1){ // 如果可以轉移到自己的必勝態，則可以獲勝
show(1);
}else{
show(0);
}
}
}
}
return 0;
}
J.Joy of Handcraft（線段樹）
思路：稍微預處理一下，然后直接線段樹暴力模擬就好了，因為題目給的t可能是相同的，那么對于相同的t，只保存最大的那個，因為最多只有n種t，那么總的復雜度就是 log(n)*n*log(n)，因為 (n/1+n/2+n/3+n/4+…+n/n) = n*log(n)
AC代碼:
#include <bits/stdc++.h>
#define int long long
#define showcase cout<<"Case #"<<cas++<<": ";
using namespace std;
int T,cas = 1;
int n,m;
struct node{
int t,x;
node(){}
}a[100050];
int tree[100050<<8];
int lazy[100050<<8];
void push_down(int pos){
int lson = pos<<1;
int rson = pos<<1|1;
lazy[lson] = max(lazy[lson],lazy[pos]);
lazy[rson] = max(lazy[rson],lazy[pos]);
tree[lson] = max(tree[lson],lazy[pos]);
tree[rson] = max(tree[rson],lazy[pos]);
lazy[pos] = 0;
}
void push_up(int pos){
tree[pos>>1] = max(tree[pos>>1],tree[pos]);
}
void build(int pos,int l,int r){
tree[pos] = lazy[pos] = 0;
if(l == r) return;
int lson = pos<<1;
int rson = pos<<1|1;
int mid = (l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
}
void update(int pos,int x,int l,int r,int ll,int rr){
if(ll <= l && rr >= r){
lazy[pos] = max(lazy[pos],x);
tree[pos] = max(tree[pos],x);
return;
}
int lson = pos<<1;
int rson = pos<<1|1;
int mid = (l+r)>>1;
if(lazy[pos]) push_down(pos);
if(ll <= mid) update(lson,x,l,mid,ll,rr);
if(rr > mid) update(rson,x,mid+1,r,ll,rr);
}
int ask(int pos,int l,int r,int x){
if(l == r){
if(l == x) return tree[pos];
else return 0;
}
int lson = pos<<1;
int rson = pos<<1|1;
int mid = (l+r)>>1;
if(lazy[pos]) push_down(pos);
if(x <= mid) return ask(lson,l,mid,x);
if(x > mid) return ask(rson,mid+1,r,x);
}
bool cmp(node a1,node a2){
if(a1.t == a2.t) return a1.x > a2.x;
return a1.t < a2.t;
}
signed main(){
cin>>T;
a[0].t = 0;
while(T--){
cin>>n>>m;
for(int i = 1 ; i <= n ; i ++){
cin>>a[i].t>>a[i].x;
}
sort(a+1,a+n+1,cmp);
build(1,1,m);
for(int i = 1 ; i <= n; i ++){
if(a[i].t != a[i-1].t){
for(int j = min(m,a[i].t),pre = 1; j <= m ; j = min(m,j+2*a[i].t)){
//cout<<pre<<"--"<<j<<endl;
update(1,a[i].x,1,m,pre,j);
pre = j+a[i].t+1;
if(j == m) break;
}
}
}
showcase;
for(int i = 1 ; i < m ; i ++){
cout<<ask(1,1,m,i)<<" ";
}
cout<<ask(1,1,m,m)<<endl;
}
}
K.Knowledge is Power（打表，找規律）
思路：找規律，分類討論也可以，但是比賽的時候分了半天還分錯了，最后DFS打表發現了36個一次回圈，直接水過了，
AC代碼：
#include <bits/stdc++.h>
#define int long long
#define showcase cout<<"Case #"<<cas++<<": ";
using namespace std;
int a[100050];
int T,cas = 1;
int n,m;
int res1[] = {1,-1,1,2,1,3,1,2,1,4};
int res2[] = {4,1,2,1,2,1,2,1,4,1,2,1,3,1,2,1,2,1,2,1,3,1,2,1,3,1,2,1,2,1,2,1,3,1,2,1};
int maxx = 0;
vector<int> res;
int gcd(int x,int y){
if(x < y) swap(x,y);
return y == 0 ? x : gcd(y,x%y);
}
void dfs(int x,int sum,vector<int> nums){
if(sum > n) return;
if(sum == n){
for(int i = 0 ; i < nums.size() ; i ++){
for(int j = 0 ; j < nums.size() ; j ++){
if(i == j) continue;
if(gcd(nums[i],nums[j]) != 1){
return;
}
}
}
if(nums[nums.size()-1]-nums[0] < maxx){
maxx = nums[nums.size()-1]-nums[0];
res.clear();
for(int i = 0 ; i < nums.size() ; i ++){
res.push_back(nums[i]);
}
}
}
if(nums.size() >= 3) return;
nums.push_back(x);
dfs(x+1,sum+x,nums);
dfs(x+2,sum+x,nums);
dfs(x+3,sum+x,nums);
dfs(x+4,sum+x,nums);
nums.pop_back();
}
signed main(){
cin>>T;
while(T--){
cin>>n;
n -= 5;
showcase;
if(n > 9) cout<<res2[(n-9)%36]<<endl;
else cout<<res1[n]<<endl;
// n += 5;
for(n = 5 ; n <= 10000 ; n ++){
// if(n == 6){cout<<-1<<endl;continue;}
// maxx = 10;
// for(int i = 2; i < n ; i ++){
// vector<int> nums;
// dfs(i,0,nums);
// }
// cout<<res[res.size()-1]-res[0]<<endl;
// if((n-13)%36 == 0) cout<<endl;
// for(int i = 0 ; i < res.size(); i++){
// cout<<res[i]<<" ";
// }
// cout<<endl;
// }
//showcase;
}
}
L.Lottery（思維，二進制）
思路：首先對于每一位，最多只要留下2個就好了，剩下的往后一直進位就好了，然后就預處理成了很多連續的非零的塊， 對于每個塊， 都是相互獨立不影響的，因為每個位上最大是2，對于一個塊，最多只能往最高位進位一位， 如果一個位上是1，那么就有0，1兩種方案，而如果一個位置上是2，就有0，1，進位，三種方案，如果進位的話，增加的方案數，就是在他后面連續的非0個數，
更一般的解釋：如果一個塊 1122112 從左往右數，對于第一個2增加 22種方案，對于第二個2增加23種方案，對于第三個2增加26種方案， 可以想象，令當前位進位，那么當前位為往后都是0，最高位為1，而前面的位可以選擇0，1兩種狀態，按112212舉例：如果第一個2進位：xx000001，x兩種狀態，所以就是22種，
最后把每個塊的方案數相乘就好了，因為互不影響
AC代碼：
#include <bits/stdc++.h>
#define int long long
#define showcase cout<<"Case #"<<cas++<<": ";
using namespace std;
const int mod = 1e9+7;
int T,cas = 1;
int n,m;
struct node{
int x,cnt;
node(){}
node(int xx,int cc){
x = xx;
cnt = cc;
}
}a[100050],que[3200050];
int qpow(int a,int b){
int res = 1;
int tmp = a;
while(b){
if(b&1) res = res*tmp%mod;
b >>= 1;
tmp = tmp*tmp%mod;
}
return res%mod;
}
bool cmp(node a1,node a2){
return a1.x < a2.x;
}
signed main(){
//rand_test(); return 0;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//freopen("out3.txt","w",stdout);
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
for(int i = 0 ; i < n ; i ++){
scanf("%lld%lld",&a[i].x,&a[i].cnt);
}
sort(a,a+n,cmp);
int tail = 0;
for(int i = 0 ; i < n; i ++){
que[tail] = a[i];
while(que[tail].cnt > 2){
int tmp = (que[tail].cnt-1)>>1;
if(i+1 >= n || que[tail].x+1 != a[i+1].x){
que[tail+1] = node(que[tail].x+1,tmp);
que[tail].cnt -= tmp<<1;
++ tail;
}else{
a[i+1].cnt += tmp;
que[tail].cnt -= tmp<<1;
}
}
++ tail;
}
int pre = 0,now = 0,res = 1,tmp = 1;
for(int i = 0 ; i < tail ; i ++){
if(i >= 1){
if(que[i].x != que[i-1].x+1){
res = (res*(qpow(2,now)+pre)%mod)%mod;
pre = 0;
now = 0;
tmp = 1;
}
}
++ now;
pre += (que[i].cnt&1) ? 0 : tmp;
pre %= mod;
tmp = (tmp<<1)%mod;
}
res = (res*(qpow(2,now)+pre)%mod)%mod;
printf("Case #%lld: %lld\n",cas++,res);
}
}
小結：前一天沒睡好，打比賽完全不在狀態，純屬摸魚，靠著隊友的快速三題混進了銅牌區，最后兩小時博弈也沒推出來，不過依然還是打星，等于花錢訓練了一波
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/208001.html
標籤：其他
上一篇：初入Python(一) Pygame貪吃蛇游戲的撰寫與改進
下一篇：關于機械鍵盤的一些基礎知識