| A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|
| \(\checkmark\) | \(\checkmark\) | \(O\) | \(\checkmark\) | \(\checkmark\) | \(O\) | \(\checkmark\) | \(O\) | \(O\) | \(\times\) |
\(\checkmark\):代表比賽時通過,
\(O\):代表賽后補題通過,
\(\times\):代表目前還未通過,
A. honoka和格點三角形
題目鏈接
題目大意
在一個\(n\)行\(m\)列的矩陣點陣中求出滿足一下要求的三角形的個數:
- 三角形的三個頂點均為格點(橫縱坐標均為整數),
- 三角形的面積為\(1\),
- 三角形至少有一條邊和\(x\)軸或者\(y\)軸平行,
解題思路
三角形的面積為\(1\),并且橫縱坐標均為整數,那么分為兩種情況(平行\(x\)軸或者\(y\)軸的為底邊):
- 底邊為\(1\),高為\(2\),
- 底邊為\(2\),高為\(1\),
再根據底邊平行的軸不同,分為四種情況即可,
AC代碼
#include<bits/stdc++.h>
const int mod = 1e9+7;
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int main()
{
ll y,x;
cin>>y>>x;
ll res;
if(x>=3)
res = ((2LL*(y-1)*(x-2))%mod)*(x-2+y)%mod;
if(y>=3)
res+= ((2*(x-1)*(y-2))%mod)*(x+y-2)%mod;
res%=mod;
cout<<res<<endl;
}
總結
規律總結題,
B. kotori和bangdream
題目鏈接
題目大意
每個音符有\(x\%\)的概率得\(a\)分,有\((100-x)\%\)的概率得\(b\)分,求\(n\)個字符的得分期望,
解題思路
求出\(n\)個字符分為全部為\(a\)分和\(b\)的得分,乘以對應的概率即為答案,
AC代碼
#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int main()
{
double n,x,a,b;
cin>>n>>x>>a>>b;
a*=n;
b*=n;
a*=x;
a/=100;
b*=(100-x);
b/=100;
printf("%.2f",a+b);
return 0;
}
總結
簽到題,但由于自己的粗心,沒有注意浮點數的使用,在比賽程序中遇到除運算的時候,應當小心一點,
C. umi和弓道
題目鏈接
題目大意
在二維坐標中有一個起始點\((x_0,y_0)\)與其他\(n\)個點相連構成\(n\)條射線,在\(x\)軸或者\(y\)軸上放一個擋板,切斷兩點之間的連接,現求擋板的最小長度以使沒有被切斷的連線的數量不超過\(k\)
解題思路
\(n\)個點中與起始點在同一象限的點是不可能被擋板給擋住的,那么分別統計與起始點不在同一象限的點與起始點的連線在\(x\)軸和\(y\)軸的交點,題目求沒有被擋板擋住的連線不超過\(k\),換言之就是要擋住至少\(n-k\)個點,然后找出連續\(n-k\)個點構成區間的最小值,
AC代碼
#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
vector<double>v1,v2;
int main()
{
double x0,y0;
cin>>x0>>y0;
int n,k;
cin>>n>>k;
k=n-k;
for(int i=0;i<n;i++){
double x1,y1;
cin>>x1>>y1;
double a=(y0-y1),b =(x1-x0);
if(x1*x0<0){
double jiao=a/b*x0+y0;
v2.push_back(jiao);
}
if(y1*y0<0){
double jiao=x0+b/a*y0;
v1.push_back(jiao);
}
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
double res=1e18;
if(v1.size()>=k){
int st=0,ed=st+k-1;
while(ed<v1.size()){
res=min(res,v1[ed]-v1[st]);
st++,ed++;
}
}
if(v2.size()>=k){
int st=0,ed=st+k-1;
while(ed<v2.size()){
res=min(res,v2[ed]-v2[st]);
st++,ed++;
}
}
if(res==1e18)cout<<"-1"<<endl;
else printf("%.7lf",res);
return 0;
}
總結
D. hanayo和米飯
題目鏈接
題目大意
有\(1,2,3 \cdots,n\)個數字,現在從中任意拿走一個數字,根據剩下的\(n-1\)個數字,判斷拿走的數字是多少,
解題思路
-
方案1:直接排序
將輸入的\(n-1\)個數字存在一個陣列當中,排一個序,遍歷陣列,如果數字的下標和數字不相等,即為答案,
-
方案二:求和
在輸入的過程中求出\(n-1\)個數字的和,再根據高斯公式求出\(n\)個數字的和,兩個相減即為答案,
AC代碼
#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int a[maxn];
int main()
{
int n;
cin>>n;
for(int i=0;i<n-1;i++){
cin>>a[i];
}
sort(a,a+n-1);
for(int i=0;i<n;i++){
if(a[i]!=i+1){
cout<<i+1<<endl;
break;
}
}
return 0;
}
總結
簽到題,
E. rin和快速迭代
題目鏈接
題目大意
給你一個式子\(f(x)\)表示\(x\)的正整數因子的個數,不斷迭代\(f(x)\)的結果,求最終結果為\(2\)時的迭代次數,
解題思路
直接模擬題意迭代即可,剛開始拿到這道題的時候,以為有什么規律,所以一開始的方向就錯了,
時間復雜度為\(O(\sqrt{n})\),
AC代碼
#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int solve(ll x){
int cnt=0;
for(ll i=2;i*i<=x;i++){
if(x%i==0){
cnt+=2;
if(i*i==x)cnt--;
}
}
return cnt;
}
int main()
{
ll n;
cin>>n;
int res=0;
ll mid=solve(n)+2;
while(mid!=2){
res++;
mid=solve(mid)+2;
// cout<<mid<<endl;
}
res++;
cout<<res<<endl;
return 0;
}
總結
在做題的程序中一定要重視計算時間復雜度,最開始以為直接模擬會炸,所以沒有去寫,往找規律的方向去思考去了,耽誤了時間,同時要注意資料的范圍,這道題就犯了這個錯誤,
F. maki和tree
題目鏈接
題目大意
在一個有\(n\)個點的樹上,每個點被標記為白色或者黑色,問有多少條只包含一個黑點的簡單路徑,
解題思路
簡單路徑只有兩種情況下會包含一個黑點:
- 起始點和終點都為白點,
- 兩個斷點其中一個是黑點,
這道題個人認為切入點為黑點,因為路徑中只有一個黑點,那么這個黑點要么為起始或者重點,要么將多個白點連接起來作為中間點,這樣一來就要找到黑點連接的白點所在的聯通塊總共有多少個白點,因為是在樹上,所以每個聯通塊是各自獨立的,不存在重復計算的情況,計算聯通塊中節點的個數可以用并查集,并查集中在連接兩個節點的時候,統計其所在父親的孩子數量,這樣其他節點所在聯通塊的節點數量為其父親節點的孩子數量加\(1\),
假設某一個黑點,連接了\(k\)個節點,其中\(f(i)\)表示第\(i\)個節點所在聯通塊的節點個數:
- 第一種情況的計算結果為\(\sum_{i=1}^k{\sum_{j=i+1}^k}f(i)*f(j)\),
- 第二種情況的計算結果為\(\sum_{i=1}^kf(i)\),
AC代碼
#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int n;
string color;
vector<int>G[maxn];
int pre[maxn];
void init(){
for(int i=0;i<maxn;i++){
pre[i]=i;
}
}
int childnum[maxn];
int nodenum[maxn];
int find(int x)
{
int r=x;
while(r!=pre[r]){
r=pre[r];
}
int i=x,j;
while(i!=pre[i]){
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void uni(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy){
pre[fx]=fy;
childnum[fy]+=childnum[fx]+1;
}
}
ll sum[maxn];
ll solve(vector<int>temp){
ll res=0;
for(int i=0;i<temp.size();i++){
res+=temp[i];
}
//求前綴和
for(int i=0;i<temp.size();i++){
sum[i+1]=sum[i]+temp[i];
}
for(int i=1;i<temp.size();i++){
res+=temp[i]*sum[i];
}
return res;
}
int main()
{
// freopen("data.txt","r",stdin);
cin>>n;
cin>>color;
//對并查集陣列進行初始化
init();
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
if(color[x-1]=='W'&&color[y-1]=='W'){
uni(x,y);
}
}
ll res=0;
for(int i=1;i<=n;i++){
nodenum[i]=childnum[find(i)]+1;
}
for(int i=1;i<=n;i++){
if(color[i-1]=='B'){
vector<int>temp;
for(int j=0;j<G[i].size();j++){
if(color[G[i][j]-1]=='W')
temp.push_back(nodenum[G[i][j]]);
}
res+=solve(temp);
}
}
cout<<res<<endl;
return 0;
}
總結
本以為自己對并查集的掌握比較牢靠,但這道題還是沒有做的出來,唉!這道題用并查集來做的思維還是比較獨特,希望自己多多積累經驗,
G. eli和字串
題目鏈接
題目大意
給你一個只包含小寫字母的字串,求滿足有\(k\)個相同字母的子串的最小長度,
解題思路
利用二維陣列,分別統計\(26\)種字母的位置,如果每種字母的個數都小于\(k\),那么就不存在這樣的字串,輸\(-1\),
對于每一種字母的情況,遍歷每一行,\(i\)下標對應的值表示第\(1\)個字母出現的位置,\(i+k-1\)下標對應的值表示第\(k\)個字母出現的位置,維護區間最小值即可,
AC代碼
#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
vector<int>a[30];
int main()
{
int n,k;
cin>>n>>k;
string str;
cin>>str;
for(int i=0;i<str.size();i++){
a[str[i]-'a'].push_back(i);
}
int maxlen=0;
for(int i=0;i<26;i++){
int len = a[i].size();
maxlen=max(len,maxlen);
}
if(maxlen<k){
cout<<"-1"<<endl;
return 0;
}
int res=2e5+10;
// cout<<a[1][0]<<" "<<a[1][1]<<endl;
for(int i=0;i<26;i++){
if(a[i].size()<k)continue;
for(int j=0;j<a[i].size()&&j+k<=a[i].size();j++){
res = min(res,a[i][j+k-1]-a[i][j]+1);
}
// cout<<res<<endl;
}
cout<<res<<endl;
return 0;
}
總結
簡單的統計,沒有什么難度,
H. nozomi和字串
題目鏈接
題目大意
給你一個長度為\(n\)只包含\(01\)字符的字串,擁有\(k\)次操作將字符\(0\)變為\(1\)或者將\(1\)改變為\(0\),問經過最多\(k\)次操作(\(k\)次機會可以不用完)之后字符相同的子串的最長長度,
解題思路
總體思路是貪心,先考慮\(k\)大于等于\(1\)的個數或者大于\(0\)的個數的情況,那么結果就是字串的長度;另一種情況則統計每一個\(1\)的前綴\(1\)和后綴\(1\)的位置,然后遍歷一遍,以\(start\)為起點,\(end\)為終點,貪心\(k\)個1的位置,將這\(k\)個\(1\)都改變為\(0\),那么字串區間為為下標\(end+1\)的值減去下標\(start-1\)的值再加\(1\),
AC代碼
/*
H題補題
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
string str;
cin>>str;
vector<int>v[2];
v[0].push_back(-1);
v[1].push_back(-1);
for(int i=0;i<str.size();i++){
if(str[i]=='0')
v[0].push_back(i);
else
v[1].push_back(i);
}
int res=0;
if(v[0].size()-1<=k||v[1].size()-1<=k)res=n;
for(int i=0;i<2;i++){
for(int j=1;j<v[i].size()&&j+k<=v[i].size();j++){
res=max(res,v[i][j+k]-v[i][j-1]-1);
}
}
cout<<res<<endl;
return 0;
}
總結
最開始在做這道題的時候想的太過于復雜,想到用動態規劃去做,沒有往貪心上靠,
I. nico和niconiconi
題目鏈接
題目大意
給你一個長度為\(n\)的字串,其中"nico" 計\(a\)分,"niconi" 計\(b\)分,"niconiconi" 計\(c\)分,求出字串最多能得多少分,(已經計算過的字符不能重復進行計算)
解題思路
利用動態規劃的思想,\(dp[i]\)表示前\(i\)個字符的最大值,轉移方程為:
\[\begin{align} &if(i>=3\&\&substr(i-3,4)=nico)dp[i]=max(dp[i],dp[i-3]+a)\\ &if(i>=5\&\&substr(i-5,6)=niconi)dp[i]=max(dp[i],dp[i-5]+b)\\ &if(i>=9\&\&substr(i-9,10)=niconiconi)dp[i]=max(dp[i],dp[i-9]+c)& \end{align} \]
AC代碼
#include<bits/stdc++.h>
const int maxn=3e5+10;
typedef long long ll;
using namespace std;
ll dp[maxn];
int main()
{
int n,a,b,c;
cin>>n>>a>>b>>c;
string str;
cin>>str;
int len=str.size();
dp[0]=0;
for(int i=1;i<len;i++){
dp[i]=dp[i-1];
if(i>=3&&str.substr(i-3,4)=="nico")
dp[i]=max(dp[i],dp[i-3]+a);
if(i>=5&&str.substr(i-5,6)=="niconi")
dp[i]=max(dp[i],dp[i-5]+b);
if(i>=9&&str.substr(i-9,10)=="niconiconi")
dp[i]=max(dp[i],dp[i-9]+c);
}
cout<<dp[len-1]<<endl;
return 0;
}
總結
動態規劃還是自己的弱點啊,根本沒有想到這方面,其實理解之后還是蠻簡單的,但就是當時看到這道題過題人數不是很多,給自己造成了心理壓力,先入為主,
轉載請註明出處,本文鏈接:https://www.uj5u.com/houduan/67292.html
標籤:C++
上一篇:洛谷P1014 Cantor表
下一篇:結題報告
