先写总结，临近蓝桥杯了，刷刷以往的蓝桥杯真题练练手，发现蓝桥杯的题简单，思路容易想，而且以暴力解法居多，当中数学计数题最多，你平时想问题是往优化方面想对这个比赛就不太适应了，所以要转变下思维，而且赛制是OI 赛制，搞ICPC的表示严重不适应，明明好不容易相出正确思路，就是因为代码细节问题没写好，不对可就亏大发了，考验的一发AC的代码能力
当中也有一些比较不错的题，有矩阵快速幂，有树形dp（目前就刷到这两个有质量的）
由于数学计数题居多 感觉也特别适合我，我组合数学计数有点差。
解法：可以三层for循环暴力，当然我是优化的，先将c的平方用map预处理一下，然后就变成两层for循环了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,int>mp;
const int M=1e2+10,N=1e4;
void init()
{
for(int i=1;i*i<=N;++i){
mp[i*i]=i;
}
}
int main()
{
int n;
init();
while(~scanf("%d",&n))
{
int f=0;
for(int i=1;i*i<=n;++i){
for(int j=i;j*j<=n;++j){
int d=i*i+j*j;
if(mp[n-d]&&j<=mp[n-d]){
f=1;
printf("%d %d %d\n",i,j,mp[n-d]);
}
}
}
if(!f){
puts("No Solution");
}
}
return 0;
}
n<1000
这类题要是在多校肯定 n特大特大，你需要每个月每个月的遍历，由于这里的n特别小，只需要按天遍历即可。
#include<bits/stdc++.h>
using namespace std;
int year[2][20]={
{0,31,28,31,30,31,30,31,31,30,31,30,31},
{0,31,29,31,30,31,30,31,31,30,31,30,31}
};
int runyear(int x)
{
if(x%400==0) return 1;
if(x%4==0&&x%100!=0) return 1;
return 0;
}
int main()
{
int a,b,c,n;
while(~scanf("%d%d%d%d",&a,&b,&c,&n))
{
for(int i=1;i<=n;++i){
++c;
int ty=runyear(a);
if(c>year[ty][b]){
c=1;
b++;
}
if(b>12) b=1,a++;
}
printf("%d-%02d-%02d\n",a,b,c);
}
}
刚开始以为这题是什么组合数学题，自己算了半天没点方法，然后想想，这是暴力杯啊，n<=13，暴力给我dfs即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
void dfs(int id,int num,int tot)
{
//printf("id:%d num:%d tot:%d\n",id,num,tot);
//if(dp[id][num]) return dp[id][num];
if(tot>=13){
if(tot==13) ans++;
return ;
}
if(num<4) dfs(id,num+1,tot+1);
if(id<13) dfs(id+1,0,tot);
}
int main()
{
dfs(1,0,0);
printf("%lld\n",ans);
}
这题跟上面那题一样，给我暴力dfs即可，注意 标记转动和翻转的，免得重复计算
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,int>mp;
int dp[4];
ll ans;
ll run(ll x)
{
queue<int>que;
while(x) que.push(x%10),x=x/10;
ll res=0;
while(que.size()) res=res*10+que.front(),que.pop();
return res;
}
void dfs(int id,ll t)
{
if(id==13) {
if(mp[t]==0){
ans++;
ll f=1;
int num=0;
for(int i=1;i<=11;++i) f=f*10;
while(num<=14){
mp[t]=1;
mp[run(t)]=1;
num++;
t=t/10+(t%10)*f;
}
}
return ;
}
for(int i=1;i<=3;++i){
if(dp[i]) {
dp[i]--;
dfs(id+1,t*10+i);
dp[i]++;
}
}
}
int main()
{
dp[1]=3,dp[2]=4,dp[3]=5;
dfs(1,0);
printf("%lld\n",ans);
}
这题一眼看出dp dp[i][j] 代表第i层，顶层数字是j的方案数。转移方程随便搞搞，n<=1e9 那就套个矩阵快速幂 over
然后每层可以旋转，就是再乘上 4的n次方
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=6;
struct Martix
{
ll mat[N][N];
Martix(){}
Martix operator *(const Martix &o) const{
Martix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
for(int k=0;k<N;++k)
res.mat[i][j]=(res.mat[i][j]+this->mat[i][k]*o.mat[k][j]%mod)%mod;
return res;
}
};
Martix Martix_pow(Martix t,ll n)
{
Martix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=0;i<6;++i) res.mat[i][i]=1;
for(;n;n>>=1){
if(n&1) res=res*t;
t=t*t;
}
return res;
}
ll n,m;
int to[7]={3,4,5,0,1,2};
ll powmod(ll a,ll n)
{
ll res=1;
for(;n;n>>=1){
if(n&1) res=res*a%mod;
a=a*a%mod;
}
return res;
}
int main()
{
while(~scanf("%lld%lld",&n,&m))
{
Martix ans;
for(int i=0;i<6;++i)
for(int j=0;j<6;++j) ans.mat[i][j]=1;
for(int i=1;i<=m;++i){
int u,v;
scanf("%d%d",&u,&v);
--u;
--v;
//u=to[u];
ans.mat[to[u]][v]=0;
ans.mat[to[v]][u]=0;
}
ans=Martix_pow(ans,n-1);
ll res=0;
for(int i=0;i<6;++i)
for(int j=0;j<6;++j){
res+=ans.mat[i][j];
res=res%mod;
}
printf("%lld\n",res*powmod(4,n)%mod);
}
return 0;
}
这题一开始想歪了，想到换根dp去了，样例过不了，仔细读了读题，要求选择的点是都是相邻的。
那么设dp[i][1] 选这个点时的答案 dp[i][0]不选这个点的答案，转移方程就是：
dp[u][1]+=max({dp[v][1],dp[v][0]});
dp[u][0]+=dp[v][0];
还是有不错的题的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
vector<int>G[N];
ll dp[N][2],val[N],ans;
int n;
void dfs1(int u,int fa)
{
dp[u][1]=val[u];
for(int v:G[u]){
if(v==fa) continue;
dfs1(v,u);
dp[u][1]+=max({dp[v][1],dp[v][0]});
dp[u][0]+=dp[v][0];
}
ans=max({dp[u][1],dp[u][0],ans});
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lld",&val[i]);
for(int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(1,-1);
printf("%lld\n",ans);
return 0;
}