这套题的质量，我感觉非常OK
A - Blackjack
签到题不说啦
#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1e7+5+5e6;
using namespace std;
const ll INF=1e15+7;
const ll mod=1e9+7;
ll n,m,p;
int main()
{
scanf("%lld%lld%lld",&n,&m,&p);
ll temp=n+m+p;
if(temp>=22) printf("bust\n");
else printf("win\n");
return 0;
}
B - Palindrome-philia
签到到
不相等就+1即可
#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1e7+5+5e6;
using namespace std;
const ll INF=1e15+7;
const ll mod=1e9+7;
ll n,m,p;
char str[maxn];
int main()
{
scanf("%s",str+1);
int len=strlen(str+1);
int s=1,e=len;
int res=0;
while(s<=e)
{
if(str[s]!=str[e])res++;
s++;
e--;
}
printf("%d\n",res);
return 0;
}
C - HonestOrUnkind2
题意:
有n个人，其中诚实的人一直说真话[honest] ，不友好的人可能说真话也可能说假话.
接下来描述n个人的信息
每个人都会说 几组 x,y ，y为1时，表示第i个人说第x个人是诚实的，y为0时则表示第i个人说第x个人是不友好的
题目思路：
通过n的范围就会发现这是个状态压缩的题..
所以我们枚举二进制，0表示这个人是不友好的，1表示这个人是诚实的
这个状态合法的条件即为，与这些人说的话是否冲突。
这里坑点就来了...当这个人不友好的时候，说的话真假无所谓..
所以 如果这个人判定为0，他说的所有话都不需要去判断.
只需要判断一下，如果说真话的人，如果当前说真话的人说x为真，但枚举二进制为假，则出现矛盾，反之也成立。
Code:
#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1e7+5+5e6;
using namespace std;
const ll INF=1e15+7;
const ll mod=1e9+7;
ll n,m,p;
vector<pair<int,int>>v[25];
int vis[20];
int work(int temp)
{
for(int k=1;k<=n;k++)
{
if(temp&(1<<(k-1)))//这人说真话
{
int sz=v[k].size();
for(int j=0;j<sz;j++)
{
int x=v[k][j].first;
int y=v[k][j].second;
if(y&&!(temp&(1<<(x-1)))) return 0;
else if(!y&&(temp&(1<<(x-1)))) return 0;
}
}
}
return 1;
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&m);
for(int k=1;k<=m;k++)
{
int x,y;
scanf("%d%d",&x,&y);
v[i].push_back(make_pair(x,y));
}
}
int res=0;
for(int i=0;i<(1<<n);i++)
{
int f=work(i);
if(f)
{
int cot=0;
for(int k=1;k<=n;k++)
cot+=(i&(1<<(k-1)))?1:0;
res=max(res,cot);
}
}
printf("%d\n",res);
return 0;
}
D - Xor Sum 4
题意：
求解上述公式
题目思路：
n的范围较大，所以for循环不可能了..
所以此题考虑异或的性质，将一个数二进制分解后
1.如果第k位是0，则该位遇到 1 会产生 
2.如果第k位是1，则该为遇到 0 会产生
所以本题的结果就是，记录到第i个数之前，二进制的每一位出现0的个数，与1的个数
如果第k位为1,res+=zero*
否则第k位为0，res+=one*
Code:
复杂度:
#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1e7+5+5e6;
using namespace std;
const ll INF=1e15+7;
const ll mod=1e9+7;
ll n,m,p;
ll zero[1000];
ll one[1000];
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b%2) ans=(ans*a)%mod;
b/=2;a=(a*a)%mod;
}
return ans;
}
int main()
{
scanf("%lld",&n);
ll sum=0;
for(int i=1;i<=n;i++)
{
ll x;
scanf("%lld",&x);
for(int k=64;k>=1;k--)
{
if(x&(1ll<<(k-1)))
{
sum+=zero[k]*qpow(2,k-1);
one[k]++;
sum%=mod;
}
else
{
sum+=one[k]*qpow(2,k-1);
zero[k]++;
sum%=mod;
}
}
}
printf("%lld\n",sum);
return 0;
}
E - Balanced Path
题意：
一个n*m的网格，你可以往下走或者往右走(普通dp走法)
每个网格内 有两个权值，你需要选择一个涂成红色，另一个涂成蓝色。
问从(1,1)到(n,m) 选择一条路线，使得红色权值之和与蓝色权值之和绝对相差最小.
题目思路：
清晰记得之前刷dp的时候，刷到过一个 骨牌翻转 的问题，问最少翻转多少次使得 所有骨牌上面权值之和-下面权值之和最小。
这个题是上述题目的改进，将一维扩展到了二维
我们使用一个三维数组 
因为 (i,k) 只能由两个方向来，所以只需要判断两个方向就可以了。
注意的细节问题：
1.蓝色和红色最大的绝对值之差为：-(w+h)*80*2~(w+h)*80*2，红色全为-80，蓝色全为*80。
2.为了避免数组负数越界，我们将 第三维数组坐标 + (w+h)*80*2，使得差值永远为正，但实际差值为j- (w+h)*80*2。
3.这样的话内存会出现一些问题,80*80*160*80*2 内存就很大，但是这个题没有让你求翻转次数，只求可不可以，所以用bool类型进行转换就可以了。bool类型是int 内存的1/32 所以这个bool数组相当于开了5e6的int 空间是可以的。
所以根据我们的推导，状态转移方程即为：
Code:
复杂度 趋近于1e8
#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1e7+5+5e6;
using namespace std;
const ll INF=1e15+7;
const ll mod=1e9+7;
ll n,m,p;
int A[100][100];
int B[100][100];
int dx[2]={0,1};
int dy[2]={1,0};
bool dp[81][81][25605];
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
for(int k=1;k<=m;k++) scanf("%d",&A[i][k]);
for(int i=1;i<=n;i++)
for(int k=1;k<=m;k++) scanf("%d",&B[i][k]);
dp[1][1][A[1][1]-B[1][1]+12800]=1;
dp[1][1][B[1][1]-A[1][1]+12800]=1;
for(int i=1;i<=n;i++)
{
for(int k=1;k<=m;k++)
{
if(i==1&&k==1) continue;
for(int j=0;j<=25600;j++)
{
int temp1=A[i][k]-B[i][k];
int temp2=B[i][k]-A[i][k];
if(dp[i-1][k][j-temp1]||dp[i-1][k][j-temp2]) dp[i][k][j]=1;
if(dp[i][k-1][j-temp1]||dp[i][k-1][j-temp2]) dp[i][k][j]=1;
}
}
}
int s=12800,e=12800;
while(1)
{
if(dp[n][m][s]||dp[n][m][e]) break;
e++;
s--;
}
printf("%d\n",e-12800);
return 0;
}
F - Sum Difference
题意：
简化一下：
一段等差序列，将等差序列分为两个集合，问这两个集合的差值会有多少种可能
题目思路：
好久没写数论，差点自闭...
这题用到的细节很多，一一说来..
1.
首先我们把 这个等差序列分为 S 与 T ，因此 S+T = U ，U即为 所有数的和
我们将S-T 表示出来：S-T=S-(U-S)=2*S-U
很明显，第一点可以推断出：S-T的取值与 集合S和的取值有关
2.如果公差d==0，那么此时需要特判
3.
如果公差<0,那么咱们可以将首项与公差一并取相反数，由于是对称的，等差数列性质不会发生改变。
所以接下来我们可以大胆的假设d>0
我们现在讨论 集合S 里面，含有k个元素的情况。
那么集合s的和就可以表示为:
这其中m的范围可以推到出来：
我最大取后k项，最小取前k项。
3.
m的范围一旦确定，我们发现 包含k个元素的集合s 里面他的和的取值是在k*x+b上的一些间断点.. 因为公差d并不为1，所以这不是条线段。
我们如果想求解个数的话，可以把他变成一条线段，那么此时问题的答案就是 线段并了。
所以接下来我们要研究如何将这些点变成连续的线段
4.
所有的点都在
因为每次都差d，并且kx是确定值 很有可能出现
k=1时 ，间断点为:2 5 8 11
k=2时，间断点为:5 8 11
所以离散点可以找到一个共有的起点，一定为 mod d【最小正整数点】。
而又因为 这些点之间都差d，所以 我们将这些点 /d 之后就变成了 增量为1的连续线段！！！！
我们将整个式子 mod d后，发现即为 k*x mod d.
5.以下所说的类，即为以哪个作为起点.
所以按 kx mod d 对每一个进行归类，因为起点不同差值又相同，所以不同类里面的 离散点互不相交。
如何求每一类里面的点的个数？每一个点/d之后就可以使得原本不连续的区间连续，因为这时增量为1。
所以具体的做法就是，求一下 kx mod d 的类，对每一类里面的线段求线段并，类的和即为答案。
6.
但是上述做法，还有个缺陷就是，d的范围是 1e8，这样的话 数组是开不了的。
考虑用map 是可以的...
然后就需要在优化一个小细节：
每一个类都是 kx mod d
我们首先将 x和d 转换为互质的两个数【 等差数列 首项和 公差同时除一个数性质还是不会变】.
即 x和d / gcd(x,d)
所以 x与d 互质，这时类即为k。
我们第一层 i 枚举属于k的最小取值,每次都+d即可确定 当前类为i时 k所有的取值
将k所有取值的 离散化线段都放到set里，然后进行求线段并。
这样就不需要 开一个数组了，只需要开一个一维set即可。
Code：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=2e6+5;
using namespace std;
const ll INF=1e18;
const ll mod=1e9+7;
ll n,x,d;
ll num[200005];
set<pair<ll,ll>>s[maxn];
ll gcd(ll a,ll b)
{
if(!b)
return a;
return gcd(b,a%b);
}
int main()
{
scanf("%lld%lld%lld",&n,&x,&d);
if(d==0)
{
printf("%lld\n",x?n+1:1ll);
return 0;
}
ll t=gcd(x,d);
x/=t;
d/=t;
//printf("%lld\n",d);
num[1]=x;
if(d<0)
{
d=-d;
x=-x;
}
ll ans=0;
for(int i=2; i<=n; i++)
num[i]=num[i-1]+d;
for(int i=0; i<d; i++) //k的最小取值
{
set<pair<ll,ll>>s;
for(ll k=i; k<=n; k+=d)
{
ll temp=k*x;
ll mins=(0ll+k-1)*k/2ll,maxe=(n-k+n-1ll)*k/2ll;
s.insert(make_pair(temp/d+mins,temp/d+maxe));
}
ll en=-INF;
for(auto k=s.begin(); k!=s.end(); k++)
{
auto u=*k;
if(en<u.first)
{
ans+=u.second-u.first+1;
en=u.second;
}
else
{
if(u.second>en)
{
ans+=u.second-en;
en=u.second;
}
}
}
}
printf("%lld\n",ans);
return 0;
}
总结：
数论太薄弱了...最后这题发懵了 三个小时！
不过这套题是套好题，所以发个题解总结一下hhhhh
京公网安备 11010502036488号