模拟题 :
如果后面存在s>=s[1] 且 e>=e[1]的,那么不可能是第一个成为冠军,输出-1,否则取w[1]为ans;
- #include
- #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- #define endl '\n'
-
- using namespace std;
- typedef long long LL;
- int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b); }
- int lcm(int a,int b){ if(a==0||b==0) return 0; return (a*b)/gcd(a,b); }
- bool is_prime(int x){if(x<2) return false;
- for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
- //numbers.erase(std::unique(numbers.begin(), numbers.end()), numbers.end()); // 去重操作
- const int N = 105;
- LL n,s[N],e[N];
-
- inline void solve(){
- cin>>n;
- LL ans = 0;
- for(int i=1;i<=n;i++) cin>>s[i]>>e[i];
- LL w = s[1];
- bool tag = false;
- for(int i=2;i<=n;i++){
- if(s[i]>=w && e[i]>=e[1]){
- tag = true;
- break;
- }
- }
- if(tag)
- cout << -1 << endl;
- else
- cout << w << endl;
- return ;
- }
-
- int main()
- {
- IOS
- int _;
- cin >> _;
- // _ = 1;
- while(_ --) solve();
- return 0;
- }
贪心,只有两种可能,取a中最小值所在的一行 或 b中最小值所在的一列,求和,答案就是两个中的较小值。
- #include
- #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- #define endl '\n'
-
- using namespace std;
- typedef long long LL;
- int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b); }
- int lcm(int a,int b){ if(a==0||b==0) return 0; return (a*b)/gcd(a,b); }
- bool is_prime(int x){if(x<2) return false;
- for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
- //numbers.erase(std::unique(numbers.begin(), numbers.end()), numbers.end()); // 去重操作
- const int N = 3e5+10;
- LL n , a[N] , b[N];
-
- inline void solve(){
- cin>>n;
- LL ma = 1e9+7 , mb = 1e9+7;
- LL sa = 0 , sb = 0;
- for(int i=1;i<=n;i++){
- cin >> a[i];
- ma = min(ma , a[i]);
- sa += a[i];
- }
- for(int i=1;i<=n;i++){
- cin >> b[i];
- mb = min(b[i] , mb);
- sb += b[i];
- }
- LL ans = min(n*ma+sb,n*mb+sa);
- cout << ans << endl;
- return ;
- }
-
- int main()
- {
- IOS
- int _;
- cin >> _;
- // _ = 1;
- while(_ --) solve();
- return 0;
- }
一个排列组合问题:
假设串 : 00011 , 那么必须选2个0 , 1个1删除 , 0的选择方案为C(3 , 2) = C(3 , 1) = 3 。1的选择方案为C(2 , 1) = 2 ,选出来三个数后,这三个数删除的顺序没有要求,所以有3!种方案,总方案数=C31 *C21*3!
推及别的用例,都是获取连续的0串或1串,答案就是每个0串/1串的长度相乘,再乘以需要选择的数字个数的阶乘。
- #include
- #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- #define endl '\n'
- using namespace std;
- typedef long long LL;
- const int p = 998244353,N=2e5+10;
- string s;
-
- LL f[N],g[N];
-
- LL qmi(int a,int b){
- int res = 1;
- while(b){
- if (b & 1) res = (LL)res * a % p;
- b >>= 1;
- a = (LL) a * a % p;
- }
- return res;
- }
-
- LL get(int a,int b){
- return (LL)f[a] * g[b] % p * g[a-b] % p;
- }
-
- LL fac(LL n){ // 求阶乘
- LL fact = 1;
- for(int i=1;i<=n;i++){
- fact = fact * i % p;
- }
- return fact;
- }
-
- inline void solve(){
- cin >> s ; s = ' ' + s;
- LL n = s.size();
- LL ans = 0 , res = 1;
- vector
ant; - for(int i=1;i<=n;i++){
- int j = i+1;
- while(j<=n && s[j]==s[i]) j++;
- int len = j - i;
- ans += len - 1;
- ant.push_back(len);
- i = j - 1;
- }
- LL ma = *max_element(ant.begin(), ant.end());
- LL fa = fac(ans);
- n = ant.size();
- f[0]=1 ; g[0] = 1;
- for (int i=1;i<=ma;i++){
- f[i] = f[i-1] * i % p;
- g[i] = (LL) g[i-1] * qmi(i , p-2 ) % p;
- }
- for(LL num : ant){
- res = (res * get(num,1)) % p;
- }
- res = ( res * fa ) % p;
- cout << ans << " " << res << endl;
- }
-
- int main()
- {
- IOS
- int _;
- cin >> _;
- while(_ --) solve();
- return 0;
- }