|
【题目大意】给定一个字符串，问是否存在3个相邻位置，使字母‘A’,‘B’,‘C’各出现1次，是的话输出Yes，否则输出No
【思路】for一遍，看看是否存在这样的三个位置
【方案一】
if(s[i - 1] == 'A'&&s[i] == 'B'&&s[i + 1] == 'C')
else if(s[i - 1] == 'A'&&s[i] == 'C'&&s[i + 1] == 'B')
else (s[i - 1] == 'A'&&s[i] == 'B'&&s[i + 1] == 'C')
【方案二】
if(s[i - 1] == '.'||s[i] == '.'||s[i + 1] == '.') continue;
else if (s[i - 1] != s[i]&&s[i] != s[i + 1]&&s[i - 1] != s[i + 1])
【方案三】（完整代码）
#include<bits/stdc++.h>
using namespace std;
string s;
map<char,int>tr;
int lens;
int main()
{
cin>>s;
lens = s.size();
tr['A'] = 1;
tr['B'] = 4;
tr['C'] = 6;
for(int i = 1;i < lens - 1;i ++)
if(tr[s[i - 1]] + tr[s[i]] + tr[s[i + 1]] == 11)
{
puts("Yes");
return 0;
}
puts("No");
}
B. Cat Cycle
【题目大意】给你一个数n，A猫的位置随时间变化依次为n , n - 1,n - 2……1,n……
B猫的位置从1开始依次增加，但不能与A猫在同一位置，若AB猫在同一位置，则B猫跳一格进入下一个位置，问m秒后B猫在哪
【思路】假设n是偶数，则两只猫永远不会相遇，则ans = m % n，若ans为0，则位置为n
若n为奇数，则两只猫在第一秒后（划重点，后面按照总步数减1算，但是算完之后要加回来，建议看完后面回头看这句话）间隔为n - 2，再往后（n - 1）/ 2秒后相遇（强行再走一格）且间隔仍与第一秒时相同，因此总步数为自然走的步数+强行走的步数+最开始先加上的1步，即：1 + (m - 1) + ((m - 1) / ((n - 1) / 2)),ans = 总步数 % n ，若ans为0，则位置为n
【参考代码】
#include<bits/stdc++.h>
using namespace std;
int n,m,ji,t;
int main()
{
cin>>t;
while(t --)
{
cin>>n>>m;
if(n % 2 == 0)
{
ji = m % n;
if(ji == 0) cout<<n<<'\n';
else cout<<ji<<'\n';
}
else
{
ji = (1 + (m - 1) + ((m - 1) / (n / 2))) % n;
if(ji == 0) cout<<n<<'\n';
else cout<<ji<<'\n';
}
}
}
C. Commentary Boxes
【题目大意】你有n个物品平均分给m个人，要求不剩下，新建一个物品的代价是a，拆除一个物品的代价是b，求最小代价
【思路】如果我能够新建t1个物品达到m的倍数，那么我再建更多的代价会更大，如果我能够拆除t2个物品达到m的倍数，那么我再拆更多的代价会更大，简言之，我只需要从最少建造的个数（m - n % m）的代价（即a × 个数）和最少拆除的个数（n % m）的代价(即 b × 个数 ）中取个较小值即可。
【参考代码】
#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,a,b,ans1,ans2;
int main()
{
cin>>n>>m>>a>>b;
ans1 = b * (n % m);
ans2 = a * (m - n % m);
cout<<min(ans1,ans2);
}
D. Cards and Joy
【题目大意】有n个人，每人能拿k张牌，第i个人对某种牌Ci情有独钟，且每个人拿到j张他喜欢的牌得到的开心值为Hj,且Hj严格大于Hj - 1，总共n * k张牌
【思路】先介绍2种错误思路
本来拿到这道题我以为是个贪心，每个人都只拿自己喜欢的牌，剩下的牌丢了就行，然而兔学长仔细一想事情并不简单，喜欢相同牌的人存在竞争关系，他们新拿到一张牌的收益是不同，不能让一个人随便去拿。
然后感觉应该是个动规，每种牌相当于一个物品，每个物品的个数是一定的喜欢该种牌的人数 × k就是背包的容量，1件1件找效率太低，优化对物品进行了二进制拆分（简单说2进制能表示数，例如16可以拆成1 2 4 8 1，可以表示拿1~16所有的数，详情请搜索混合背包）然后发现1 1和2的结果不相同，虽然能够凑出每一个数，但是“单价”不一定，并且单位值可能超过k造成无法取答案。朴素的1件1件拿感觉会超时（目测4个for），果断放弃
正解1：1件1件拿（而且比网上搜到的正解快近3倍）
正解2：每个物品拿相同个数是等价的，即不管什么东西拿1件，2件，3件都是一样的价值，预处理dp[i][j]表示i个物品j个人分最多得到的最大价值，然后把每种物品加上即可
【参考代码】
（二进制拆分——错误方法）
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 505;
const int K = 5005;
long long n,k,a,ji[N],num[N],ans,hav[N],dp[M][K],ge[N],end[N],chai[N][25],cnt,sum[M];
int main()
{
cin>>n>>k;
for(int i = 1;i <= n * k;i ++)
{
cin>>a;
ji[a] ++;
if(ji[a] == (1 << ge[a]))
ge[a] ++;
chai[a][ge[a]] ++;
}
for(int i = 1;i <= n;i ++)
{
cin>>a;
if(!num[a]) end[++ cnt] = a;
num[a] ++;
}
for(int i = 1;i <= k;i ++)
{
cin>>a;
sum[i] += a;
}
for(int i = 1;i <= cnt;i ++)
{
for(int kk = 1;kk <= ge[end[i]];kk ++)
for(int j = num[end[i]] * k;j >= chai[end[i]][kk];j --)
dp[i][j] = max(dp[i][j],dp[i][j - chai[end[i]][kk]] + sum[chai[end[i]][kk]]);
ans += dp[i][num[end[i]] * k];
}
cout<<ans;
}
正解1：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 505;
const int K = 5005;
long long n,a,ji[N],num[N],ans,dp[K][M],endd[N],cnt,h[15];
int k;
int main()
{
cin>>n>>k;
for(int i = 1;i <= n * k;i ++)
{
cin>>a;
ji[a] ++;
}
for(int i = 1;i <= n;i ++)
{
cin>>a;
if(!num[a]) endd[++ cnt] = a;
num[a] ++;
}
for(int i = 1;i <= k;i ++)
cin>>h[i];
for(int i = 1;i <= cnt;i ++)
{
for(int j = 1;j <= ji[endd[i]];j ++)
{
dp[j][1] = h[min(j,k)];
for(int kk = 2;kk <= num[endd[i]];kk ++)
{
for(int l = 1;l <= min(j,k);l ++)
dp[j][kk] = max(dp[j][kk],dp[j - l][kk - 1] + h[l]);
}
}
ans += dp[ji[endd[i]]][num[endd[i]]];
}
cout<<ans;
}
正解二：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 505;
const int K = 5005;
long long n,a,ji[N],num[N],ans,dp[K][M],cnt,h[15];
int k;
int main()
{
cin>>n>>k;
for(int i = 1;i <= n * k;i ++)
{
cin>>a;
ji[a] ++;
}
for(int i = 1;i <= n;i ++)
{
cin>>a;
num[a] ++;
}
for(int i = 1;i <= k;i ++)
cin>>h[i];
for(int i = 1;i <= n * k;i ++)
{
dp[i][1] = h[min(i,k)];
for(int j = 2;j <= n; j++)
for(int l = 1;l <= min(i, k);l ++)
dp[i][j] = max(dp[i][j], dp[i - l][j - 1] + h[l]);
}
for(int i = 1; i <= 1e5;i ++)
if(num[i])
ans += dp[ji[i]][num[i]];
cout<<ans;
}
E. Xor-Paths
【题目大意】一个m*n的图，每个位置有一个数，给定特定的数t，求从左上到右下（只允许往右或者往下），求有多少种方案的异或和为t，n，m <= 20
【思路】暴搜的复杂度是2^（m + n）不符合要求
经过14次尝试
尝试方案一：利用哈希写记忆化企图萌混过关（WA于第24个点）
尝试方案二：写哈希表看脸（TLE于第24个点）
尝试方案三：黑进后台把第24个点删掉， 咳咳
正解：折半搜索（正向搜到第（m + n）/ 2步，反向搜剩下的（m + n）/ 2步）2 * 2^（m + n） / 2，符合要求
原因：记录下一部分答案，然后利用空间换时间
提问：为什么不直接用动规
回答：用动规的空间复杂度 ≈ 用暴搜的时间复杂度，会超空间
【参考代码】
哈希记忆化（牺牲一定正确率来提高效率）
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 21;
const int MOD = 1e4;
int n,m;
ull ma[N][N],ans,k;
ull used[N][N][MOD],ji[N][N][MOD];
ull hah(ull x)
{
return (x * 131 * 233) % 9991;
}
ull read()
{
ull x = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + c - '0';
c = getchar();
}
return x;
}
ull dfs(int x, int y, ull sum)
{
if(used[x][y][hah(sum)])
return used[x][y][hah(sum)];
if (x == n && y == m)
{
if (sum == k) return 1;
return 0;
}
if (ji[x][y][hah(sum)]) return 0;
ji[x][y][hah(sum)] = 1;
if (x != n)
used[x][y][hah(sum)] += dfs(x + 1, y, sum ^ ma[x + 1][y]);
if (y != m)
used[x][y][hah(sum)] += dfs(x, y + 1, sum ^ ma[x][y + 1]);
return used[x][y][hah(sum)];
}
int main()
{
n = read();m = read();k = read();
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
ma[i][j] = read();
cout<<dfs(1,1,ma[1][1]);
}
哈希表记忆化（看脸）
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 21;
const int MOD = 1e4;
int n, m;
ull ma[N][N], ans, k, cnt[N][N], nex[N][N][MOD];
ull used[N][N][MOD];
struct zt {
ull num;
ull cnt;
} ji[N][N][MOD];
ull hah(ull x) {
return (x * 131 * 233) % 9991;
}
ull read() {
ull x = 0;
char c = getchar();
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + c - '0';
c = getchar();
}
return x;
}
ull dfs(int x,int y,ull sum)
{
if(x == n && y == m)
{
if (sum == k) return 1;
return 0;
}
for(int i = used[x][y][hah(sum)];i;i = nex[x][y][i])
if(ji[x][y][i].num == sum)
return ji[x][y][i].cnt;
ji[x][y][++ cnt[x][y]] = (zt) {sum, 0};
nex[x][y][cnt[x][y]] = used[x][y][hah(sum)];
used[x][y][hah(sum)] = cnt[x][y];
if (x != n)
ji[x][y][cnt[x][y]].cnt += dfs(x + 1, y, sum ^ ma[x + 1][y]);
if (y != m)
ji[x][y][cnt[x][y]].cnt += dfs(x, y + 1, sum ^ ma[x][y + 1]);
return ji[x][y][cnt[x][y]].cnt;
}
int main()
{
n = read();m = read();k = read();
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
ma[i][j] = read();
cout<<dfs(1, 1, ma[1][1]);
}
折半搜索（需要注意中间点一定要大于2，否则正向搜索会陷入死循环，因此中间点取(m + n) / 2 + 1）
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 21;
int n,m;
ull ma[N][N],ans,k;
map<ull,ull> used[N];
ull read()
{
ull x = 0;
char c = getchar();
while(c < '0'||c > '9') c = getchar();
while(c >= '0'&&c <= '9')
{
x = (x << 1) + (x << 3) + c - '0';
c = getchar();
}
return x;
}
void dfs1(int x,int y,ull sum)
{
if(x + y == (m + n) / 2 + 1)
{
used[x][sum] ++;
return;
}
if(x != n) dfs1(x + 1,y,sum ^ ma[x + 1][y]);
if(y != m) dfs1(x,y + 1,sum ^ ma[x][y + 1]);
}
void dfs2(int x,int y,ull sum)
{
if(x + y == (m + n) / 2 + 1)
{
ans += used[x][sum ^ k ^ ma[x][y]];
return;
}
if(x != 1) dfs2(x - 1,y,sum ^ ma[x - 1][y]);
if(y != 1) dfs2(x,y - 1,sum ^ ma[x][y - 1]);
}
int main()
{
n = read();m = read();k = read();
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
ma[i][j] = read();
dfs1(1,1,ma[1][1]);
dfs2(n,m,ma[n][m]);
cout<<ans;
}
|