ICPC Time
思路：
模拟
代码：
1
2
3
4
5
6
7
8
|
void solve()
{
int n;
cin>>n;
if(n+5>=24)cout<<n+5-24;
else cout<<n+5;
}
|
倍数
思路：
检查有没有 5 或者 0。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
| void solve()
{
string n;
cin>>n;
for(int i=0;i<n.size();i++){
if(n[i]=='0'||n[i]=='5'){
cout<<"YES"<<endl;
return;
}
}
cout<<"NO"<<endl;
}
|
邻合
思路：
动态规划，设 dp[i][0] 表示第 i 个数不修改的最小次数，dp[i][1] 表示第 i 个数修改的最小次数。
状态转移方程：
还需要特判一下全为 1 的结果。注意这里的 if-else 结构如果当前位置 gcd 为 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
| const int N=2e5+5;
int a[N];
int dp[N][2];
void solve()
{
int n;
cin>>n;
memset(dp,0x3f,sizeof dp);
bool falg=true;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]!=1)falg=false;
}
if(falg){
cout<<n<<endl;
return;
}
int cnt=0;
dp[1][0]=0;dp[1][1]=1;
for(int i=2;i<=n;i++)
{
if(__gcd(a[i],a[i-1])!=1)dp[i][0]=min(dp[i-1][1],dp[i-1][0]);
else dp[i][0]=dp[i-1][1];
dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1;
}
cout<<min(dp[n][1],dp[n][0])<<endl;
}
|
补充思路：
看到大神的简单题解了，写一下理解一下。 时是肯定要修改的。当 时可以贪心将 a[i] 修改为 a[i+1]*a[i-1]。可以直接将这个数字设置成 0，这样之后计算 gcd 时会直接返回另一个数的值。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void solve()
{
int n;
cin>>n;
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(__gcd(a[i],a[i-1])==1)ans++,a[i]=0;
}
cout<<ans<<endl;
}
|
对和
思路：
模拟一下可以看出来，每个数字都会被计算 次，之后就是要处理下取整的问题，当和为奇数时就会进行下取整，即 的操作，那么统计有多少个奇数、偶数，然后进行组合一共有 组，然后计算。
代码：
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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=2e5+5;
int a[N];
void solve()
{
int n;
cin>>n;
int sum=0;
int cnt=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i]*(n-1);
if(a[i]%2)cnt++;
}
int ans=sum-cnt*(n-cnt);
cout<<ans/2<<endl;
}
signed main(){
IOS
int t;
cin>>t;
while(t--)
{
solve();
}
}
|
镜像
思路：
本质是最短路。
先来明确一下，只有个位不为 0 时才能反转，反转不会改变位数。
首先先来检测一下 a 是否比 b 大一位。如果大的话输出 -1。
之后使用队列维护每一个遇到的值，使用 pair 来存储 {当前值,到达当前值的操作次数}。这样的话可能就会遍历很多，所以能剪枝的尽量剪。
代码：
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
int a,b,k;
int rev(int x){
int res=0;
while(x>0){
res=x%10+res*10;
x/=10;
}
return res;
}
void solve()
{
cin>>a>>b>>k;
if(a==b){
cout<<"0"<<endl;
return;
}
queue<PII> q;
q.push({a,0});
int ans=-1;
int mx=1;
while(mx<b)mx*=10;
if(a>=mx){
cout<<"-1"<<endl;
return;
}
vector<int> st(mx,0);
st[a]=1;
while(!q.empty()){
auto [x,cnt]=q.front();
q.pop();
if(x%10){
int r=rev(x);
if(r==b){
ans=cnt+1;
break;
}
if(r<mx&&!st[r]){
st[r]=1;
q.push({r,cnt+1});
}
}
int m=x+k;
if(m==b){
ans=cnt+1;
break;
}
if(m<mx&&!st[m]){
st[m]=1;
q.push({m,cnt+1});
}
}
cout<<ans<<endl;
}
signed main(){
IOS
int t;
cin>>t;
while(t--)
{
solve();
}
}
|
