Cut The Wire
电线数量为左边路灯中偶数的数量加上奇数且3x + 1 > n的数量。
代码:
#include<bits/stdc++.h>
using namespace std;
int T,x,num;
int main()
{
cin>>T;
while(T -- )
{
cin>>x;
num = 0;
int t = x / 3;
if(t % 2 == 0)
{
t ++;
num = (x - t + 1) / 2;
if(x % 2 == 1)
num ++;
}
else
{
while(3 * t + 1 <= x)
t += 2;
num = (x - t + 1) / 2;
if(x % 2 == 1)
num ++;
}
if(x % 2 == 0)
cout<< x / 2 + num<<endl;
else
cout<< x / 2 + num + 1<<endl;
}
return 0;
}
Command Sequence
用map记录位置即可,就是不知道如何记录不重复的字串数量。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll n,ans,T,x,y;
char s;
map<pii,int>mp;
int main()
{
cin>>T;
while(T -- )
{
cin>>n;
x = 0,y = 0;
ans = 0;
mp.clear();
mp[ {x,y}] ++ ;
for(int i = 1; i <= n; i ++ )
{
cin>>s;
if(s == 'U')
x -- ;
else if(s == 'D')
x ++ ;
else if(s == 'L')
y -- ;
else if(s == 'R')
y ++ ;
if(mp[ {x,y}])
ans += mp[ {x,y}];
mp[ {x,y}] ++;
}
cout<<ans<<endl;
}
return 0;
}
Power Sum
关键:(x + 1) ^ 2 - (x + 2) ^ 2 - (x + 3) ^ 2 + (x + 4) ^ 2 = 4
知道了这个式子,对于 n mod 4 可以分成四种情况分别构造即可
代码:
#include<bits/stdc++.h>
using namespace std;
int T,n,k,x;
int main()
{
cin>>T;
while(T -- )
{
cin>>n;
x = n / 4;
if(n % 4 == 0)
{
cout<<n<<endl;
for(int i = 1; i <= x; i ++ )
cout<<"1001";
}
else if(n % 4 == 1)
{
cout<<n<<endl;
cout<<'1';
for(int i = 1; i <= x; i ++ )
cout<<"1001";
}
else if(n % 4 == 2)
{
cout<<n + 2<<endl;
cout<<"0001";
for(int i = 1; i <= x; i ++ )
cout<<"1001";
}
else if(n % 4 == 3)
{
cout<<n - 1<<endl;
cout<<"01";
for(int i = 1; i <= x; i ++ )
cout<<"1001";
}
cout<<endl;
}
return 0;
}
Shooting Bricks
dp[i][j][1] 表示前 i 列,用了 j 发子弹且最后一发子弹没有打在第 i 列的最大得分
dp[i][j][0] 表示前 i 列,用了 j 发子弹且最后一发子弹打在了第 i 列的最大得分
v[i][j][1] 表示第 i 列,用了 j 发子弹且最后一发子弹没有打在第 i 列的的得分
v[i][j][0] 表示第 i 列,用了 j 发子弹且最后一发子弹打在了第 i 列的得分
其余见注释
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int T,n,m,k,cnt,dp[N][N][2],v[N][N][2],g[N][N],b[N][N];
char s;
int main()
{
cin>>T;
while(T -- )
{
memset(b,0,sizeof(b));
memset(v,0,sizeof(v));
memset(dp,0,sizeof(dp));//k的存在dp也要初始化
cin>>n>>m>>k;
for(int i = 1; i <= n; i ++ )//读入数据
for(int j = 1; j <= m; j ++ )
{
cin>>g[i][j]>>s;
if(s == 'Y')
b[i][j] = 1;
}
for(int i = 1; i <= m; i ++ )//预处理v
{
cnt = 0;
for(int j = n; j >= 1; j -- )//必须从最后一排处理,否则wa
{
if(b[j][i])
v[i][cnt][1] += g[j][i];
else
{
cnt ++ ;
v[i][cnt][1] = v[i][cnt - 1][1] + g[j][i];
v[i][cnt][0] = v[i][cnt - 1][1] + g[j][i];
}
}
}
for(int i = 1; i <= m; i ++ )//枚举列
for(int j = 0; j <= k; j ++ )//枚举子弹数
for(int l = 0; l <= min(n,j); l ++ )//枚举第i列的子弹数,注意限制条件
{
//最后一发一直没有打
dp[i][j][1] = max(dp[i][j][1],dp[i - 1][j - l][1] + v[i][l][1]);
if(l)//最后一发打在第i列的条件是第i列有子弹
dp[i][j][0] = max(dp[i][j][0],dp[i - 1][j - l][1] + v[i][l][0]);
if(j - l)//最后一发打在i - 1,i - 1需要有子弹
dp[i][j][0] = max(dp[i][j][0],dp[i - 1][j - l][0] + v[i][l][1]);
}
cout<<dp[m][k][0]<<endl;
}
}