A.Hcode OnlineJudge
給出一個N面骰子和整數K，擲出1-N之間的每個數的概率相同，每次擲出一次，記為成績，若成績小于K，則開始拋硬幣，硬幣朝上則數翻倍，反之則為0，概率都為0.5。當數大于等于K或等于0時結束。求成績大于等于K的概率。
英文題目讀假了，寫不出來。其實只需要把每個數的概率分別求出來再求和就行了，注意乘上擲出該數的概率
#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5+10;
const int mod = 998244353;
int n,m,k;void sovle(){cin>>n>>m;double a,b=0.000000000;a=n*1.000000000;a=1/a;for(int i=1;i<=n;i++){int u=i;double c=1.000000000;while(u<m){c*=0.5000000000;u*=2;}b+=c*a;}printf("%.9f\n",b);
}signed main()
{ //ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); int t = 1; //cin>>t;while (t--){sovle();}return 0;
}
B.Hcode OnlineJudge
給出ABCD四個操作和一個雙端隊列，要求你通過不超過K次的操作，使得所得整數之和最大
正解應該是隊列，我用數組也過了。
數據范圍很小，四層循環暴力也能過，枚舉操作次數，左邊取的個數和右邊取的個數，剩下的次數可以用來丟掉負數
#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5+10;
const int mod = 998244353;
int n,m,k;void sovle(){cin>>n>>m;vector<int>a(n);for(int i=0;i<n;i++){cin>>a[i];}int max1=0;for(int i=0;i<=m;i++){for(int j=0;j<=i;j++){vector<int>b,c;for(int w=0;w<j;w++){b.push_back(a[w]);}for(int u=0;u<=i&&u+j<=i&&u+j<=n;u++){for(int e=n-1;e>=n-u&&e>=j;e--){b.push_back(a[e]);}if(!(u+j)) continue;c=b;sort(c.begin(),c.end());int x;x=i-j-u;int y=0;while(x>0){x--;if(c[y]<0&&y<c.size()){y++;}}int sum=0;for(;y<c.size();y++){sum+=c[y];}max1=max(max1,sum);for(int e=n-1;e>=n-u&&e>=j;e--){b.pop_back();}}}}cout<<max1<<endl;
}signed main()
{ ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); int t = 1; //cin>>t;while (t--){sovle();}return 0;
}
C.Hcode OnlineJudge
實際上就是求組成最少幾個的遞增序列。
有點像窗口排隊問題，用一個數組維護隊尾就好了，每次二分查詢現有的隊伍中小于該數的最大隊尾，并將隊尾修改成該數，如果沒有則新開一隊，也就是往后插入這個數。顯然，這個數組總是滿足非遞減的單調性，具有二分性。
#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e9+10;
const int mod = 998244353;
int n,m,k;int cmp(PII a,PII b){return a.first<b.first;
}void sovle(){cin>>n;vector<int>a(n);vector<int>b;for(int i=0;i<n;i++){cin>>a[i];}int sum=1;b.push_back(a[0]);for(int i=1;i<n;i++){int l=0,r=b.size(),ans=-1;while(l<=r&&(l+r)/2<b.size()){int mid=(l+r)>>1;if(b[mid]<a[i]){r=mid-1;ans=mid;}else{l=mid+1;}}if(ans!=-1){b[ans]=a[i];}else{b.push_back(a[i]);sum++;}}cout<<sum<<endl;
}signed main()
{ ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); int t = 1; //cin>>t;while (t--){sovle();}return 0;
}
F.Hcode OnlineJudge
給你一個N長度的序列和M個bi，ci。你可以將該序列中不超過bi個數替換成ci。求該序列最大和
暴力會超時，我們可以將全部數看成紙牌，你擁有的紙牌數就是ci張和序列中有的。那么只需要用map記錄鍵值對和值，取最大的N張就可以了，不需要考慮替換。
不會逆序遍歷map，所以我用了負數來存鍵值，這樣在后面乘上負號就可以保證是從大到小排序
#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5+10;
const int mod = 998244353;
int n,m,k;void sovle(){cin>>n>>m;map<int,int>a;for(int i=0;i<n;i++){cin>>k;a[-k]++;}for(int i=0;i<m;i++){int x,y;cin>>x>>y;a[-y]+=x;}int sum=0;for(auto ed:a){if(ed.second<=n){sum+=-ed.first*ed.second;n-=ed.second;}else{sum+=-ed.first*n;break;}}cout<<sum<<endl;
}signed main()
{ ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); int t = 1; //cin>>t;while (t--){sovle();}return 0;
}
)
)
】)
