1001、Cut The Wire
簽到題，按照題意來思考就行
開題時間：0:05
交題時間：0:39
問題：手速慢了，其次就是思考分類時過于復雜了，但又不能快速想清楚
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
ll n;
cin>>n;
if (n%2==0)//偶數
{
ll even=ceil(n/2.0);
ll t=ceil((n-1)/3.0);
if (t%2==0) t+=1;
if (3*t+1==n) t+=1;
ll odd=(n-1-t)/2+1;
cout<<even+odd<<endl;
}
else
{
ll even=ceil(n/2.0);
ll t=ceil((n-1)/3.0);
if (t%2==0) t+=1;
ll odd=(n-t)/2+1;
cout<<even+odd<<endl;
}
}
return 0;
}
1002、Time-division Multiplexing
開題時間：2:000前后
標簽：字串、雙指標、滑動視窗
相關題：
難點：讀題，轉化題意
賽中出現的問題：讀題太慢，沒選取正確的代碼(原來是二分)，導致一直TLE，誤以為是構造串的地方出了鍋，這題拖延了整體比賽節奏
題意
這一題有一定的工科背景，大概含義就是，n行字串都有一個指標，每次從第一行到最后一行取當前指標下標的字符，并且將指標后移一位，當指標指向了行末的下一位，那就回到0下標，依次重復構成一個回圈串，求一個最短子串的長度，該串能包含所有出現過的字符，
思路
用雙指標來解決最短子串，右指標每次放入，當左右指標的區間內包含的不同字符數等于所有出現過的字符數，那么就更新答案，左指標向右
重點：構造出來的串需要s+=s，原因是我們的答案，會出現在兩個串交界的地方，這也是比賽時沒想到的地方
代碼
#include <bits/stdc++.h>
using namespace std;
string str[105];
int p[105], n;
int leng[105];
const int INF=0x3f3f3f3f;
bool fun()
{
for (int i = 1; i <= n; i++)
if (0 != p[i])
return false;
return true;
}
int vis[30];
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
cin >> n;
int maxn = -1, pos;
string s = "";
int gcd;
for (int i = 1; i <= n; i++)
{
cin >> str[i];
int len = str[i].size();
if (maxn < len)
maxn = len, pos = i;
p[i] = 0;
leng[i] = len;
}
int sum=0;
memset(vis,0,sizeof vis);
do
{
for (int i = 1; i <= n; i++)
{
int now = p[i];
p[i]++;
if (p[i] >= leng[i])
p[i] = 0;
s += str[i][now];
if (vis[str[i][now]-'a']==0)
sum++;
vis[str[i][now]-'a']=1;
}
} while (!fun());
//構造出來的字串為s
//cout<<s<<endl<<s.size()<<endl;
s+=s;
memset(vis,0,sizeof vis);
int cnt=0,len=s.size(),res=INF;
for(int i=0,j=0;j<len;j++)
{
if (vis[s[j]-'a']==0)
cnt++;
vis[s[j]-'a']++;
while(cnt==sum)
{
res=min(j-i+1,res);
if (--vis[s[i]-'a']==0)
cnt--;
i++;
}
}
cout<<res<<endl;
}
return 0;
}
1006、Power Sum
開題：0:50前后
提交：1:28
隊友做的，但在思考時，想到了相鄰兩對平方差的和等于4這個結論，也想到了只要能特殊構造出1,2,3，再不停地加上4就可以了，(但隊友手速太快了直接切了%%%)
\[-(-(x+1)^2+(x+2)^2)-(x+3)^2+(x+4)^2=4 \]1: $$1^2$$
2: $$-1-4-9+16$$
3: $$-1+4$$
4: $$1-4-9+16$$
題意
給定n，讓我們通過以下式子，其中$$a_i$$可為1或者-1
\[\sum\limits_{i=1}^k a_i\times i^2 = n \]得到1~k的加減平方數的和，其和等于n，求出k和$$a_i$$的結果
代碼
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n,k=0;
cin>>n;
int cnt=n/4;
n%=4;
string str="";
if (n==1)
str="1",k=1;
else if (n==2)
str="0001",k=4;
else if (n==3)
str="01",k=2;
for(int i=0;i<cnt;i++)
str+="1001";
k+=cnt*4;
cout<<k<<endl<<str<<endl;
}
return 0;
}
1009、Command sequence
題意：
給出上下左右的指令，求有多少子串能夠回到初始點
思路
說白了就是求機器人是否經過一個點一次以上，有的話那么答案就加一
向上就+1，向下-1，向左+1000007,向右-1000007
如果now出現在map中，那么就代表之前走到過這
代碼
#include<bits/stdc++.h>
using namespace std;
const int M=1e6+7;
typedef long long ll;
map<ll,ll> mp;
int main(){
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
ll now=0,res=0;
mp.clear();
int n;
cin>>n;
string cmd;
cin>>cmd;
mp[0]=1;//回到起點
for(int i=0;i<n;i++)
{
if (cmd[i]=='U')
now+=1;
if (cmd[i]=='D')
now-=1;
if (cmd[i]=='L')
now+=M;
if (cmd[i]=='R')
now-=M;
res+=mp[now];
mp[now]++;
}
cout<<res<<endl;
}
return 0;
}
1011、Shooting Bricks
這道題是在比賽最后一小時才看的，當時一直在調1002題，但是我看1011通過數比較多才看了一下，第一反應就是貪心或者dp
但出于沒有思路就放棄掉了
賽后補題也花了一個下午才搞明白
如果本隊按照賽中的0罰時，加上1002，1011題，加3次左右的罰時，那么應該能夠達到rank300左右
題意
有n行m列的磚頭，每個磚塊都有一個價值，每打掉一個磚就要花費一顆子彈，有些標記成'Y'的磚是不花費子彈的，求：當你有K顆子彈時，最多能得到多少價值？
思路
思路是賽后看得題解做出來的
我們將子彈花費轉化成我們的背包模型的空間
先預處理一下，我們在第j列上，花費cnt顆子彈，能夠得到多少的價值
\[vy[i][j]$$代表在第i列花費j時得到的恰好到'Y'的磚塊 $$vn[i][j]$$代表在第i列花費j時得到的恰好到'N'的磚塊 $$fy[i][j]$$代表從1到i列，在第i列上花費j顆子彈，并且恰好最后一顆打在了'Y'磚塊上的最大總價值 $$fn[i][j]$$代表從1到i列，在第i列上花費j顆子彈，并且恰好最后一顆打在了'N'磚塊上的最大總價值 ## 代碼 ```c++ #include<bits/stdc++.h> using namespace std; const int N=250; int fy[N][N],fn[N][N],a[N][N],st[N][N],vn[N][N],vy[N][N]; int main(){ ios::sync_with_stdio(false); int T; cin>>T; while(T--) { memset(fy,0,sizeof fy); memset(fn,0,sizeof fn); memset(vn,0,sizeof vn); memset(vy,0,sizeof vy); int n,m,k; cin>>n>>m>>k; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { char ch; cin>>a[i][j]>>ch; st[i][j]=(ch=='Y'); } //預處理 for(int j=1;j<=m;j++) { int cnt=0; for(int i=n;i>=1;i--) { if (st[i][j]) { vy[j][cnt]+=a[i][j]; //cout<<"j:"<<j<<"cnt:"<<cnt<<" "<<vy[j][cnt]<<endl; } else { cnt++; vn[j][cnt]=vy[j][cnt-1]+a[i][j]; vy[j][cnt]=vn[j][cnt]; } } } for(int i=1;i<=m;i++)//列舉列 for(int j=0;j<=k;j++)//1~i列花費j for(int l=0;l<=min(j,n);l++)//在第i列花費l { // fy[i][j]=max(fy[i][j],fy[i-1][j-l]+vy[i][l]); if (l==j) fn[i][j]=max(fn[i][j],fy[i-1][j-l]+vn[i][l]); else if (l==0) fn[i][j]=max(fn[i][j],fn[i-1][j-l]+vy[i][l]); else fn[i][j]=max(fn[i][j],max(fy[i-1][j-l]+vn[i][l],fn[i-1][j-l]+vy[i][l])); //cout<<i<<' '<<j<<' '<<k<<' '<<fn[i][j]<<endl; } cout<<fn[m][k]<<endl; } return 0; } ``` 后續還需要補1013，1012、Remove可能要放棄了\]轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296239.html
標籤：其他
上一篇：KMP演算法