A 小红的 7
思路：
打表
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| map<string,int>mp;
void solve()
{
string s;
cin>>s;
int n=6;
cout<<mp[s]<<endl;
}
signed main(){
IOS
int t=1;
cin>>t;
mp["142857"]=1;
mp["285714"]=2;
mp["428571"]=3;
mp["571428"]=4;
mp["714285"]=5;
mp["857142"]=6;
while(t--)
{
solve();
}
}
|
B 小红的回文串
思路：
别问我为什么 WA 三发。
找中间连续的长度就行。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
| void solve()
{
int n;
cin>>n;
string s;
cin>>s;
int l=(n-1)/2;
int r=n/2;
while(l>=0&&r<n&&s[l]==s[r]){
l--,r++;
}
cout<<r-l-1<<endl;
}
|
C 小红的 gcd 位运算构造
思路：
二进制吧，按位与结果为 0 说明 y 的二进制为 1 的位置都在 x 的二进制位为 0 的位置。
如果是偶数直接输出 1 即可。如果是奇数，那么从低位开始找 x 的二进制第一个为 0 的位置 i， 输出。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void solve()
{
int x;
cin>>x;
int ans=1;
if(x%2==0){
cout<<"1"<<endl;
return;
}
for(int i=0;i<31;i++){
if(((x>>i)&1)==0){
ans=ans<<i;
cout<<ans<<endl;
break;
}
}
}
|
D i 在西元前
思路：
模拟吧。
复数乘法：
一个复数序列
等比即
所以可以检验 ,写成 $z_2z_{i-1}=z_1z_i$
所以用循环去检查就行。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #define YES cout<<"Yes\n";
#define NO cout<<"No\n";
const int N=1e5+5;
int a[N],b[N];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
bool flag=1;
for(int i=2;i<=n;i++){
int aa,bb,c,d;
aa=a[i]*a[1]-b[i]*b[1];
bb=a[i]*b[1]+a[1]*b[i];
c=a[i-1]*a[2]-b[i-1]*b[2];
d=a[i-1]*b[2]+b[i-1]*a[2];
if(aa!=c||bb!=d){
flag=0;
break;
}
}
if(flag)YES
else NO
}
|
E 小红打游戏
思路：
0/1 背包+完全背包。直接套板子就行。
二维数组开不了那么大，直接把上限都卡在 就行。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| const int N=2e4+5;
int a[N],b[N],c[N];
int dp[1100][1100];
void solve()
{
int n,k;
cin>>n>>k;
int x,y;
cin>>x>>y;
for(int i=0;i<=x;i++){
for(int j=0;j<=y;j++)dp[i][j]=1e18;
}
dp[0][0]=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i];
}
for(int i=1;i<=k;i++){
for(int j=x;j>=0;j--){
for(int p=y;p>=0;p--){
if(dp[j][p]==1e18)continue;
int mx=min(x,j+a[i]);
int my=min(y,p+b[i]);
dp[mx][my]=min(dp[mx][my],dp[j][p]+c[i]);
}
}
}
for(int i=k+1;i<=n;i++){
for(int j=0;j<=x;j++){
for(int p=0;p<=y;p++){
if(dp[j][p]==1e18)continue;
int mx=min(x,j+a[i]);
int my=min(y,p+b[i]);
dp[mx][my]=min(dp[mx][my],dp[j][p]+c[i]);
}
}
}
if(dp[x][y]!=1e18){
cout<<dp[x][y]<<endl;
}else cout<<"-1"<<endl;
}
|
