【瓜分5000元奖金】Wannafly挑战赛13
鏈接:https://www.nowcoder.com/acm/contest/80/A
來源:牛客網
空間限制:C/C++ 262144K,其他語言524288K
64bit IO Format: %lld
題目描述
學家zzy根據字體的特點,創建了一系列小號...??I_Love_Chtholly!
滿足以下四種情況之一,所顯示的字符是一樣的
1、兩個字符互為英文字母的大小寫
2、大寫的'i'和小寫的'l'
3、大寫的'o'和數字'0'
4、基于前三種情況,三個字符a,b,c,如果a和b顯示相同,b和c顯示相同,那么a和c顯示也是相同的
珂學家zzy想知道,對于一個他看起來相同的昵稱,有多少個看起來一樣的昵稱
兩個字符串看起來一樣當且僅當長度一樣且每個對應的位置的字符看起來一樣
輸入描述:
一個字符串,只包含大小寫字母和數字輸出描述:
共一行一個整數,表示看起來一樣的昵稱數,由于這個數比較大,所以只要求輸出模1e9 + 7意義下的解 示例1輸入
abcdl輸出
64說明
第一個位置、第二個位置、第三個位置、第四個人位置都只有兩種顯示相同的字符第五個位置有四種顯示相同的字符
備注:
字符串長度1<=|S|<=1e5第三條規則看了一年,枚舉了一年,就是特殊字符支持來回轉換,那就乘*2,*3,*4的差別
#include<bits/stdc++.h> using namespace std; const int MD=1e9+7; int main() {string s;cin>>s;int n=1;for(int i=0;s[i];i++)if(s[i]>='1'&&s[i]<='9')continue;else if(s[i]=='I'||s[i]=='l'||s[i]=='i'||s[i]=='L')n=n*1LL*4%MD;else if(s[i]=='O'||s[i]=='0'||s[i]=='o')n=n*1LL*3%MD;else n=n*2%MD;cout<<n;return 0; }鏈接:https://www.nowcoder.com/acm/contest/80/B
來源:??途W
空間限制:C/C++ 262144K,其他語言524288K
64bit IO Format: %lld
題目描述
在文某路學車中學高一新生軍訓中,Jxc正站在太陽下站著軍姿,對于這樣的酷熱的陽光,Jxc?表示非常不爽。
Jxc將天空看做一個n*n的矩陣,此時天上有m朵云,這些云會隨機分布在m個不同的位置,同時太陽會隨機出現在一個位置,Jxc想知道他被太陽曬到的概率是多少,由于他仍在站軍姿,所以這個有趣的問題就交給了你??紤]到精度問題,Jxc只需要知道這個概率在對998244353取模意義下的值。
Tips:一個分數p/q在模意義下的值即p*q-1在模意義下的值,Xp-11 (mod p)
輸入描述:
輸入只有一行,包含兩個整數n、m。n和m的意義見題面.輸出描述:
第一行包含一個整數Ans,為答案 示例1輸入
2 2輸出
499122177備注:
1 <= n, m <= 2000,m <=n^2幾何概型,答案就是(n*n-m)/(n*n),直接逆元
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MD=998244353LL; int INV(ll x) {return x==1?x:1LL*(MD-MD/x)*INV(MD%x)%MD; } int main() {ll n,m;cin>>n>>m;cout<<(n*n-m)*INV(n*n)%MD;return 0; }鏈接:https://www.nowcoder.com/acm/contest/80/C
來源:牛客網
空間限制:C/C++ 262144K,其他語言524288K
64bit IO Format: %lld
題目描述
一個8?*?8的棋盤,第一個格子放1個麥穗,第二個格子放2個麥穗,第三個格子放4個麥穗……那么最后,共要放幾個麥穗呢?
zzf表示這個問題實在太簡單,于是重新規定了游戲的規則。
初始的棋盤為空,棋盤大小為p*p,然后他要對棋盤進行若干次操作,可以被選擇的操作如下:
1、選擇一行,每個格子再放一個麥穗
2、選擇一列,每個格子再放一個麥穗
進行若干次操作后,如果得到的棋盤滿足如下性質
1、每個格子都有至少一個麥穗
2、每個格子最多只能有p*p個麥穗
3、任意兩個格子的麥穗數不同
如果滿足以上三條,那么稱這個棋盤是一個好棋盤,若只是構造一個好棋盤那就太沒意思了,zzf想知道他能得到多少個不同的好矩陣
定義不同的矩陣即只要存在一個位置不同即是不同的
答案對998244353取模
輸入描述:
第一行讀入一個數p,表示這個棋盤的大小輸出描述:
輸出一行包括一個數,表示好棋盤的個數 示例1輸入
2輸出
8說明
樣例解釋 :1 2
3 4
3 4
1 2
1 3
2 4
2 4
1 3
2 1
4 3
4 3
2 1
3 1
4 2
4 2
3 1
備注:
2 <= p <= 1e6, 保證p是質數其實要填的東西是一定的啊,每個矩陣要加的次數是(1+n*n)*n/2假設橫行值大于豎行,你會發現其實只有一種填法的,而且每個數都不同,就是他的全排列,行列不同就是兩倍
感謝biu哥的真情繪圖
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MD=998244353LL; int main() {ll p,ans=1;cin>>p;for(int i=1;i<=p;i++)ans=ans*i%MD;cout<<ans*ans%MD*2%MD;return 0; }鏈接:https://www.nowcoder.com/acm/contest/80/D
來源:??途W
空間限制:C/C++ 262144K,其他語言524288K
64bit IO Format: %lld
題目描述
? 最可愛的applese生日啦,他準備了許多個質量不同的蛋糕,想請一些同學來參加他的派對為他慶生,為了不讓一部分同學感到不爽,他決定把每個蛋糕都分割成幾份(也可以不分割),使得最小的蛋糕的質量與最大的蛋糕的質量的比值不小于一個值。但是applese的刀功并不是很好,所以他希望切盡量少的刀數使得所得到的蛋糕滿足條件。由于applese為了保證每一塊蛋糕的質量和期望的沒有偏差,所以他一刀只能切下一塊蛋糕,即將一塊蛋糕分成兩塊,同時,他不能一刀同時切兩塊蛋糕,也就是說,applese一次只能將一塊蛋糕分割成兩塊指定質量的蛋糕,這兩塊蛋糕的質量和應等于切割前的蛋糕的質量。Applese還急著準備各種派對用的飾品呢,于是他把這個問題交給了你,請你告訴他至少要切割幾次蛋糕
輸入描述:
第一行包括兩個數T,n,表示有n個蛋糕,最小的蛋糕的質量與最大的蛋糕的質量的比值不小于T接下來n行,每行一個數wi,表示n個蛋糕的質量
輸出描述:
輸出包括一行,為最小切割的刀數數據保證切割次數不超過500 示例1
輸入
0.99 3 2000 3000 4000輸出
6備注:
0.5 < T < 11 <= n <= 1000
1 <= wi <= 1000000
暴力切的刀數,但是要處理精度問題的,不然就T了
#include<bits/stdc++.h> using namespace std; int w[1005],a[1005]; double eps=1e-10; int main(){int n;int ans=-1;double t;cin>>t>>n;for(int i=0;i<n;i++)cin>>w[i];for(int i=0;i<=500;i++){int flag;double maxx=0;double maxxb=0;double minn=10000000;for(int j=0;j<n;j++){double tmp=w[j];if(tmp/(a[j]+1)>maxx){maxx=tmp/(a[j]+1);flag=j;}if(fabs(tmp/(a[j]+1)-maxx)<eps){if(w[j]>w[flag])flag=j;}maxxb=max(maxxb,tmp/(a[j]+1));minn=min(minn,tmp/(a[j]+1));}if(minn/maxxb-t>=0){ans=i;break;}else{a[flag]++;}}cout<<ans<<endl;return 0;}?鏈接:https://www.nowcoder.com/acm/contest/80/E
來源:牛客網
空間限制:C/C++ 262144K,其他語言524288K
64bit IO Format: %lld
題目描述
VVQ?最近迷上了線段這種東西
現在他手上有?n?條線段,他希望在其中找到兩條有公共點的線段,使得他們的異或值最大。?定義線段的異或值為它們并的長度減他們交的長度
輸入描述:
第一行包括一個正整數 n,表示 VVQ 擁有的線段條數。接下來 n 行每行包括兩個正整數 l,r,表示 VVQ 擁有的線段的 左右端點。
輸出描述:
一行一個整數,表示能得到的最大異或值 示例1輸入
3 10 100 1 50 50 100輸出
99說明
選擇第二條和第三條,99-0=99備注:
1<=n<=200000,1<=l<=r<=1e8可以作為線段樹模板,用線段樹用更新的,甚至堆可以過
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; struct T {int l,r;bool operator <(const T p)const{return l+r>p.l+p.r;} } p[N]; bool cmp(T a,T b) {return a.l==b.l&&a.r<b.r||a.l<b.l; } int main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n;cin>>n;for(int i=0; i<n; i++)cin>>p[i].l>>p[i].r;sort(p,p+n,cmp);priority_queue<T>Q;Q.push(p[0]);int r=p[0].r,l=p[0].r-p[0].l,ans=0;for(int i=1; i<n; i++){if(p[i].r>r)r=p[i].r,l=p[i].r-p[i].l;elseans=max(ans,l-(p[i].r-p[i].l));while(!Q.empty()&&Q.top().r<p[i].l)Q.pop();if(!Q.empty())ans=max(ans,(p[i].l+p[i].r)-(Q.top().l+Q.top().r));Q.push(p[i]);}cout<<ans<<"\n";return 0; }?
轉載于:https://www.cnblogs.com/BobHuang/p/8759682.html
總結
以上是生活随笔為你收集整理的【瓜分5000元奖金】Wannafly挑战赛13的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: python无法对存在交叉部分的图片进行
- 下一篇: 离散数学集合论与数理逻辑基本概念