慢跑
这题完全是在针对我
还是题意没有充分理解
- 设跑步者B 跑步如果追上A 那么A速度就降为一样 然后后面的那位C原本追不上可能就追上了
- 如果B追不上 C不可能追上B
设每组的领跑者的位置和速度 如果他追不上前面那位或者是最后以为则为领跑者
一道模拟题居然卡那么久 哭了
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
#define ll long long
ll a[maxn],b[maxn];
int main()
{
ll n,t;
scanf("%lld%lld",&n,&t);
for(ll i=1; i<=n; ++i)
{
scanf("%lld%lld",&a[i],&b[i]);
}
ll ans=n;
ll pre=b[n],pos=a[n];
for(ll i=n-1; i>=1; --i)
{
if(a[i]+b[i]*t>=pos+pre*t)
{
ans--;
}
else
{
pos=a[i];
pre=b[i];
}
}
printf("%lld\n",ans);
return 0;
}迷宫问题
- DFS求到终点的方案数
很基础的DFS 可能写得太少都忘了
起点的标记要注意
然后每次遇到DFS都有种莫名的恐惧？
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=102;
int s[maxn][maxn];
bool vis[maxn][maxn];
int n,ans;
int dx[]= {0,0,1,-1,1,-1,-1,1};
int dy[]= {1,-1,0,0,1,-1,1,-1};
void dfs(int x,int y){
for(int i=0; i<8; ++i){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx==1&&yy==n){
ans++;
return;
}
if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!s[xx][yy]&&!vis[xx][yy]){
vis[xx][yy]=true;
dfs(xx,yy);
vis[xx][yy]=false;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j)
scanf("%d",&s[i][j]);
}
vis[1][1]=true;
dfs(1,1);
printf("%d\n",ans);
return 0;
}星区
对题意坐标的理解…..其实也很好理解
然后就是DFS求连通块
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=55;
int s[maxn][maxn][maxn];
bool vis[maxn][maxn][maxn];
int n;int X,Y,Z,m;
int dx[]={0,0,-1,1,0,0};
int dy[]={1,-1,0,0,0,0};
int dz[]={0,0,0,0,1,-1};
void dfs(int x,int y,int z,int p){
vis[x][y][z]=true;
for(int i=0; i<6; ++i){
int xx=x+dx[i];
int yy=y+dy[i];
int zz=z+dz[i];
if(xx>=1&&xx<=X&&yy>=1&&yy<=Y&&zz>=1&&zz<=Z&&!vis[xx][yy][zz]&&abs(s[xx][yy][zz]-p)<=m)
{
dfs(xx,yy,zz,s[xx][yy][zz]);
}
}
}
int main(){
scanf("%d%d%d%d",&X,&Y,&Z,&m);
for(int i=1;i<=X;++i){
for(int j=1;j<=Y;++j){
for(int k=1;k<=Z;++k){
scanf("%d",&s[i][j][k]);
}
}
}
int ans=0;
for(int i=1;i<=X;++i){
for(int j=1;j<=Y;++j){
for(int k=1;k<=Z;++k){
if(!vis[i][j][k]){
dfs(i,j,k,s[i][j][k]);
ans++;
}
}
}
}
printf("%d\n",ans);
return 0;
}冠军剑士
- BFS求最短路径
这三个题算是搜索的基础题
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int cx[]={0,0,1,-1,1,-1,1,-1};
int cy[]={1,-1,1,-1,0,0,-1,1};
bool vis[101][101];
int stx,sty,enx,eny;
inline bool check(int x,int y){
if(x>=1&&x<=n&&y>=1&&y<=m) return true;
return false;
}
struct node{
int x,y;
int step;
}st,en;
int bfs(){
queue<node>que;
st.x=stx;
st.y=sty;vis[st.x][st.y]=true;
st.step=0;
que.push(st);
while(!que.empty()){
st=que.front();
que.pop();
if(st.x==enx&&st.y==eny){
return st.step;
}
for(int i=0;i<4;++i){
int xx=st.x+dx[i];
int yy=st.y+dy[i];
if(!vis[xx][yy]&&check(xx,yy)){
en.x=xx;
en.y=yy;
en.step=st.step+1;
vis[xx][yy]=1;
que.push(en);
}
}
}
return 0;
}
int main() {
int t;
scanf("%d%d%d%d%d%d%d",&n,&m,&stx,&sty,&enx,&eny,&t);
int u,v;
for(int i=1;i<=t;++i){
scanf("%d%d",&u,&v);
vis[u][v]=1;
for(int j=0;j<8;++j){
int xx=u+cx[j];
int yy=v+cy[j];
if(check(xx,yy)){
vis[xx][yy]=1;
}
}
}
printf("%d\n",bfs());
return 0;
}帝国交通
题意要求几个需要联系的王国之间建立最短的道路，然后道路只能建在相邻的两点，并且是环．
数组开两倍然后断环为链 这是基本操作
因为有些区间正更优，有些反过来优，通过枚举链上的起点，这样就可以枚举到所有的情况
左端点+1 右端点-1 for一遍就让res不停加上该位置的值，如果不是0则证明这段需要建路
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=20005;
const int maxm=2000;
struct node
{
int l,r;
} s[maxn];
int f[maxm];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; ++i)
{
scanf("%d%d",&s[i].l,&s[i].r);
if(s[i].l>s[i].r) swap(s[i].l,s[i].r);
}
int ans=n;
for(int i=0; i<n; ++i){
int st=1+i;
int en=n+i;
int res=0,tmp=0;
memset(f,0,sizeof(f));
for(int j=1;j<=m;++j){
if(s[j].l>=st){
f[s[j].l]++;
f[s[j].r]--;
}
else if(s[j].l<st&&s[j].r<st){
f[s[j].l+n]++;
f[s[j].r+n]--;
}
else if(s[j].l<st&&s[j].r>=st){
f[s[j].l+n]--;
f[s[j].r]++;
}
}
for(int j=st; j<=en; ++j){
res+=f[j];
if(res>0){
tmp++;
}
}
ans=min(tmp,ans);
}
printf("%d\n",ans);
return 0;
}矩阵快速幂
设矩阵\(A\)
\[ S=A^1+A^2+A^3+....+A^n \]
直接用矩阵快速幂然后加起来肯定超时
这题可以用等比数列求和的方法 但是矩阵不能除 算逆阵有点麻烦
把这个矩阵拆成两个部分 就是
\[ S=A^1+A^2+A^3+....+A^{n/2}+A^{n/2}*(A^1+A^2+A^3+....+A^{n/2}) \]
然后通过递归 奇数再加上\(A^{n/2+1}\)就好了
matrix expmod(matrix a,int n)//快速幂
{
e.init();
while (n)
{
if(n & 1) e=e*a;
a=a*a;
n>>=1;
}
return e;
}
matrix solve(int k)//二分
{
if(k==1) return a;
c=solve(k>>1);
matrix ans=c+c*expmod(a,(k>>1));
if(k & 1) ans=ans+expmod(a,k);
return ans;
}也可以通过构造嵌套矩阵的方法来求
\[ \begin{matrix} A&A \\ 0&E \\ \end{matrix} \tag{1} \]
发财兔序列
注意审题：非降序列
记下每种数的起点 每个位置属于哪种树
查询时两边的数可以通过其到起点的距离来得出
而中间的数则转化为查询区间最大值
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+1;
int stmax[maxn][20],stmin[maxn][20];
int poww[25],logg[maxn];
int n,q;
int findll[maxn];
int ll[maxn];
int a[maxn],cnt[maxn];
void init(){
poww[0]=1;
for(int i=1; i<=20; i++)//预处理次方
{
poww[i]=poww[i-1]<<1;
}
for(int i=2; i<=n; i++)
{
logg[i]=logg[i>>1]+1;
}
int temp=1;
for(int j=1; j<=logg[n]; j++)//temp=2^(j-1)
{
for(int i=1; i<=n-temp-temp+1; i++)
{
stmax[i][j]=max(stmax[i][j-1],stmax[i+temp][j-1]);
}
temp<<=1;
}
}
inline int query_max(int l,int r){
if(r<l) return 0;
int len=r-l+1;
int k=logg[len];
return max(stmax[l][k],stmax[r-poww[k]+1][k]);
}
int main(){
int num;n=0;
scanf("%d",&num); scanf("%d",&q);
for(int i=1;i<=num;++i){
scanf("%d",&a[i]);
if(a[i-1]!=a[i]||i==1){
n++;
cnt[n]++;
findll[i]=n;
ll[n]=i;
}
else{
cnt[n]++;
findll[i]=n;
}
}
for(int i=1;i<=n;++i){
stmax[i][0]=cnt[i];
}
init();int u,v;
while(q--){
scanf("%d%d",&u,&v);
if(findll[u]==findll[v]){
printf("%d\n",v-u+1);
}
else{
int tmp=max(cnt[findll[u]]-u+ll[findll[u]],v-ll[findll[v]]+1);
printf("%d\n",max(tmp,query_max(findll[u]+1,findll[v]-1)));
}
}
return 0;
}发财兔fbi树
- 后序遍历：先左后右再到根
有点像线段树的递归
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+7;
char s[1028];
void gao(int l,int r){
if(r>l){
gao(l,(l+r)>>1);
gao(((l+r)>>1)+1,r);
}
int fo=0,tmp=0;
for(int i=l;i<r;++i){
if(s[i]!=s[i+1]){
fo=1;
}
}
if(fo){
cout<<'F';
}
else if(!fo&&s[l]=='0'){
cout<<'B';
}
else if(!fo&&s[l]=='1'){
cout<<'I';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
cin>>s+1;
int tmp=1<<n;
gao(1,tmp);
return 0;
}滑动窗口
强行用ST表水过去
实际上应该用单调队列
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+7;
int s[maxn];int q[maxn],p[maxn],k;
void solve_max(int n){
int head=1;
int tail=0;
for(int i=1;i<=n;++i){
while(head<=tail&&q[tail]<=s[i]) tail--;
q[++tail]=s[i];
p[tail]=i;
while(p[head]<=i-k)head++;
if(i>=k)printf("%d ",q[head]);
}
printf("\n");
}
void solve_min(int n){
int head=1;
int tail=0;
for(int i=1;i<=n;++i){
while(head<=tail&&q[tail]>=s[i]) tail--;
q[++tail]=s[i];
p[tail]=i;
while(p[head]<=i-k)head++;
if(i>=k)printf("%d ",q[head]);
}
printf("\n");
}
int main(){
int n;scanf("%d%d",&n,&k);
for (int i = 1; i <=n ; ++i) {
scanf("%d",&s[i]);
}
solve_min(n);
memset(p,0,sizeof(p));
memset(q,0,sizeof(q));
solve_max(n);
return 0;
}发财兔求和
推公式，找出重复计算的部分优化
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000+1;
const int mod = 10007;
struct node{
ll x;
ll val;
}s[maxn];
ll dp[2][maxn];
ll num[2][maxn];
int main(){
ll n,m;scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;++i) {
scanf("%lld", &s[i].val);
}
for(ll i=1;i<=n;++i){
scanf("%lld",&s[i].x);
dp[i%2][s[i].x]=(s[i].val+dp[i%2][s[i].x])%mod;
num[i%2][s[i].x]=(num[i%2][s[i].x]+1)%mod;
}
ll ans=0;
for(int i=1;i<=n;++i){
ans=(ans+i*((num[i%2][s[i].x]-2)*s[i].val%mod+dp[i%2][s[i].x])%mod)%mod;
}
printf("%lld\n",ans);
return 0;
}有趣的数
- 当\(n\)是10的倍数的时候，位置一定是 $\log_{10}k $，如果不是的话就返回0
- 当n不是10的倍数:
- 如果位置小于n为最大数时n的位置，返回0
- 如果位置等于n为最大数时n的位置，返回n
- 大于的话，就让len++，让n增大,模拟找到合适的位置
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
string a;
ll pos,s[10];
ll gao(){
int len=(int)a.length();
ll ans=0,p=0,log=1;
for(int i=0;i<len;++i){
s[i]=a[i]-'0';
p=p*10ll+s[i];
ans+=p-log;
log*=10ll;
if(i!=len-1) ans++;
}//ans为比n小的有多少
if(ans+1==pos)return p;
if(p*10==log)return 0;
if(pos<ans+1) return 0;
while(1){
p*=10ll;
if(ans+1+p-log>=pos){
return log+pos-ans-2;
}//pos-(ans+1)是差多少位 加上log-1就是答案
ans+=p-log;
log*=10ll;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;cin>>t;
while(t--){
cin>>a>>pos;
cout<<gao()<<endl;
}
return 0;
}
matrix
神奇的暴力瞎搞
行与行之间可以相互交换 枚举列 那么每行只用在意当前列有没有1 1最多能延伸多少
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5000+5;
bool arr[maxn][maxn];
int cnt[maxn];
int ans;char str;
int pos[maxn];int n,m;
inline void gao(){
for(register int i=m;i>=1;--i){
ans=max(ans,i*cnt[i]);
cnt[i-1]+=cnt[i];
cnt[i]=0;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>str;
if(str=='0')arr[i][j]=0;
else arr[i][j]=1;
}
}
for(register int j=1;j<=m;++j){
for(register int i=1;i<=n;++i){
if(!arr[i][j]) continue;
if(pos[i]<j)pos[i]=j;
while(pos[i]<=m&&arr[i][pos[i]+1]) pos[i]++;
cnt[pos[i]-j+1]++;
}
gao();
}
cout<<ans<<endl;
return 0;
}发财兔1C
［l,r］内的卡片所有出现了偶数次的数的异或和是多少
可以转化为区间不同的数的个数与区间所有数的异或和
因为如果一个数出现偶数次 那么这个数异或和为０，奇数则为原来的数
这样就会把原序列中奇数个数的数都去掉
区间不同数通过离线查询,记录这个数最后出现的位置，然后树状数组来实现
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
int pre_sum[maxn],unq_sum[maxn],n,q;
inline int lowbit(int x){
return x&(-x);
}
ll getsum(int pos){
ll res=0;
for(ll i=pos;i>0;i-=lowbit(i)){
res^=unq_sum[i];
}
return res;
}
void add(int pos,int val){
for(int i=pos;i<=n;i+=lowbit(i)){
unq_sum[i]^=val;
}
}
struct node{
int l,r,id;
bool operator<(const node &c)const{
return r<c.r;
}
}s[maxn];
struct find_last{
int val,id;
bool operator<(const find_last &c)const{
if(val==c.val){
return id<c.id;
}
else return val<c.val;
}
}copy_num[maxn];
int num[maxn];
int last[maxn];
int ans[maxn];
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i){
scanf("%d",&num[i]);
copy_num[i].val=num[i];
copy_num[i].id=i;
pre_sum[i]=pre_sum[i-1]^num[i];
}
for(int i=1;i<=q;++i){
scanf("%d%d",&s[i].l,&s[i].r);
s[i].id=i;
}
sort(s+1,s+1+q);int pos=1;
sort(copy_num+1,copy_num+n+1);
for(int i=2;i<=n;++i){
if(copy_num[i].val==copy_num[i-1].val){
last[copy_num[i].id]=copy_num[i-1].id;
}
}
for(int z=1;z<=q;++z){
while(pos<=s[z].r){
if(last[pos]) add(last[pos],num[pos]);
add(pos,num[pos]);
pos++;
}
ans[s[z].id]=getsum(s[z].r)^getsum(s[z].l-1)^pre_sum[s[z].r]^pre_sum[s[z].l-1];
}
for(int i=1;i<=q;++i){
printf("%d\n",ans[i]);
}
return 0;
}桥桥的告白
审题 充分理解题意
记录过程 然后向上递归查询a喜欢b b喜欢c c喜欢d之类的
找到最原始被喜欢的那个人
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long long
const int maxn=1005;
const int maxm=300000+1;
int pos[maxm][2];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;cin>>n;
char s[maxn][25];
for(register int i=1;i<=n;++i){
cin>>s[i];
}
int m;cin>>m;
for(register int i=1;i<=m;++i){
cin>>pos[i][0]>>pos[i][1];
}
int pre=1;
for(register int i=m;i>=1;--i){
if(pos[i][0]==pre){
pre=pos[i][1];
cout<<"I_love_";
}
}
cout<<s[pre]<<endl;
return 0;
}菱菱的旅途
贪心策略
左右端点 先缩小的那个端点 然后找到最大值
因为缩小小的必然优于缩大的 然后就可以不重不漏找到枚举所有可能情况
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long long
const int maxn=1000000+5;
ll s[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1; i<=n; ++i) scanf("%lld",&s[i]);
ll l=1,r=n;
if(n==1) printf("%lld\n",s[1]);
else
{
ll ans=min(s[1],s[n])*n;
while(l<=r)
{
if(s[l]<=s[r]) l++;
else if(s[l]>s[r])r--;
ans=max(min(s[l],s[r])*(r-l+1),ans);
}
printf("%lld\n",ans);
}
return 0;
}鑫鑫的算术
跟a and b和a or b有关的题要联想到二进制
可以发现这个单纯是二进制1的重组 如何让1重组成最大的数 当然是每位尽量都是1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;
int wei[35];
ll p_pow[35];
void count_one(int n){
int res=0;
while(n){
if(n&1) wei[res]++;
n>>=1;
res++;
}
}
void init(){
p_pow[0]=1;
for(int i=1;i<=32;++i){
p_pow[i]=p_pow[i-1]*2ll;
}
}
ll gao(){
bool flag=0;
ll res=0;
for(int i=32;i>=0;--i){
if(wei[i]){
flag=1;
res=res+p_pow[i];
wei[i]--;
if(res>=mod) res-=mod;
}
}
if(flag==0) return -1;
return res;
}
int main(){
int n;scanf("%d",&n);
int a;
init();
for(int i=1;i<=n;++i){
scanf("%d",&a);
count_one(a);
}
ll ans=0;
ll tmp=gao();
while(tmp!=-1){
ans+=tmp*tmp%mod;
if(ans>=mod) ans-=mod;
tmp=gao();
}
printf("%lld\n",ans%mod);
return 0;
}排队
由题意可知，可以分成很多个链．枚举x所在的链前面有多少链，然后得到可能的位置
可以用dp来求，也可以用bitset这个骚操作
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1005;
int n,x,fa[maxn];
bool vis[maxn];
int main(){
scanf("%d%d",&n,&x);
for(int i=1;i<=n;++i){
scanf("%d",&fa[i]); vis[fa[i]]=true;
}int res,p,flag;
vector<int>vt;
for(int i=1;i<=n;++i){
if(vis[i])continue;
else{
res=0;p=i;flag=0;
while(p){
res++;
flag|=(x==p);
p=fa[p];
}
if(!flag) vt.push_back(res);
}
}
bitset<maxn>dp; dp[0]=1;
for(auto x:vt) dp|=(dp<<x);
p=x;int c=0;
while(p){
c++;p=fa[p];
}
for(int i=0;i<=n;++i){
if(dp[i]) printf("%d\n",i+c);
}
return 0;
}
DAVE打扑克
两堆合并用并查集
虽然堆数可能很多，但是不同数量堆最多有1e3个
cnt[i]记录牌数为i的有多少个
相同牌数的贡献是cnt[i] * (cnt[i]-1)/2
不同牌数的贡献是cnt[i] * cnt[j]
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+7;
ll n,m;
ll fa[maxn];
set<ll>st;
ll val[maxn];
ll cnt[maxn];
ll que[maxn*5];
ll Size;
ll findfa(ll x){
if(fa[x]==x) return x;
else return fa[x]=findfa(fa[x]);
}
void add(ll u,ll v){
ll f1=findfa(u);
ll f2=findfa(v);
if(f1!=f2){
cnt[val[f1]]--;cnt[val[f2]]--;
if(!cnt[val[f1]]) st.erase(val[f1]);
if(!cnt[val[f2]]) st.erase(val[f2]);
fa[f1]=f2;
val[f2]+=val[f1];
cnt[val[f2]]++;
st.insert(val[f2]);
Size--;
}
}
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;++i){
fa[i]=i;
val[i]=1;
}
cnt[1]=n;
st.insert(1);
ll op,pos,u,v;
Size=n;
for(ll i=1;i<=m;++i){
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld",&u,&v);
add(u,v);
}
else{
scanf("%lld",&pos);
set<ll>::iterator it=st.begin();
ll tail=0,head=0,pre=0;
ll ans=0;
while(it!=st.end()){
while(head<tail&& *it-que[head]>=pos){
pre-=cnt[que[head]];
head++;
}
ans+=cnt[*it]*pre;
if(pos>0) ans+=(cnt[*it]*(cnt[*it]-1))/2;
que[tail++]=*it;
pre+=cnt[*it];
it++;
}
printf("%lld\n",Size*(Size-1)/2-ans);
}
}
return 0;
}
You Like the Cake
对于100的数据，N≤40，X,Vi≤109
背包容量过大采用折半之后二进制枚举子集，再二分查找
upper_bound返回的是第一个大于查找的数的位置
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[25],b[25];
ll s[(1<<21)+1],f[(1<<21)+1];
int main(){
int n;
ll m;scanf("%d%lld",&n,&m);
for(int i=1;i<=n;++i){
if(i<=n/2){
scanf("%lld",&a[i]);
}
else scanf("%lld",&b[i-n/2]);
}
int k=n/2;
int pos=0;
for(int i=0;i<(1<<k);++i){
for(int j=1;j<=k;++j){
if(i&(1<<(j-1))){
s[pos]+=a[j];
}
}
pos++;
}
int len=(int)(unique(s,s+pos)-s);
sort(s,s+len);
pos=0;k=n-k;
for(int i=0;i<(1<<k);++i){
for(int j=1;j<=k;++j){
if(i&(1<<(j-1))){
f[pos]+=b[j];
}
}
pos++;
}
ll ans=0;
int op;
for(int i=0;i<pos;++i){
if(m<f[i]) continue;
op=upper_bound(s,s+len,m-f[i])-s;
op--;
if(op>=0){
ans=max(ans,s[op]+f[i]);
}
}
printf("%lld\n",m-ans);
return 0;
}
花
刚开始感觉是组合数学…没想到是跟喝汤差不多的一道DP．
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
#define ll long long
ll dp[maxn][4][2];
const int mod=1e9+7;
void init(ll s){
memset(dp,0,sizeof(dp));
dp[1][1][0]=s;
}
int main(){
int t;scanf("%d",&t);
while(t--) {
ll n, s;
scanf("%lld%lld", &n, &s);
init(s);
for(int i=2;i<=n;++i){
dp[i][1][0]=(dp[i-1][1][0]*(s-1)%mod+dp[i-1][2][0]*(s-1)%mod)%mod;
dp[i][2][0]=dp[i-1][1][0];
dp[i][3][1]=dp[i-1][2][0];
dp[i][1][1]=((dp[i-1][1][1]*(s-1)%mod+dp[i-1][2][1]*(s-1)%mod)%mod+dp[i-1][3][1]*(s-1)%mod)%mod;
dp[i][2][1]=dp[i-1][1][1];
}
ll res=0;
res=((dp[n][1][1]+dp[n][2][1])%mod+dp[n][3][1])%mod;
printf("%lld\n",res);
}
return 0;
}
五子棋
模拟 斜线那个注意一下．
#include <bits/stdc++.h>
using namespace std;
int mapp[250][250];
bool check_updown(int x,int y)
{
int sum=1;
for(int i=x+1;i<=225;++i){
if(mapp[x][y]==mapp[i][y]) sum++;
else break;
}
for(int i=x-1;i>=1;--i){
if(mapp[x][y]==mapp[i][y]) sum++;
else break;
}
if(sum>=5) return 1;
return 0;
}
bool check_rightle(int x,int y)
{
int sum=1;
for(int i=y+1;i<=225;++i){
if(mapp[x][y]==mapp[x][i]) sum++;
else break;
}
for(int i=y-1;i>=1;--i){
if(mapp[x][y]==mapp[x][i]) sum++;
else break;
}
if(sum>=5) return 1;
return 0;
}
bool check_rightxie(int x,int y)
{
int sum=1;
for(int i=1;x+i<=225&&y+i<=225;++i){
if(mapp[x][y]==mapp[x+i][y+i]) sum++;
else break;
}
for(int i=1;x-i>=1&&y-i>=1;++i){
if(mapp[x][y]==mapp[x-i][y-i]) sum++;
else break;
}
if(sum>=5) return 1;
return 0;
}
bool check_leftxie(int x,int y)
{
int sum=1;
for(int i=1;x+i<=225&&y-i>=1;++i){
if(mapp[x][y]==mapp[x+i][y-i]) sum++;
else break;
}
for(int i=1;x-i>=1&&y+i<=225;++i){
if(mapp[x][y]==mapp[x-i][y+i]) sum++;
else break;
}
if(sum>=5) return 1;
return 0;
}
int check_all(int x,int y)
{
if(check_leftxie(x,y)||check_updown(x,y)||check_rightle(x,y)||check_rightxie(x,y))
{
return 1;
}
return 0;
}
int main()
{
int t;
scanf("%d",&t);
int x,y;
int flag=0;
for(int i=1; i<=t; ++i)
{
scanf("%d%d",&x,&y);
if(flag) continue;
if(i%2==1)
{
mapp[x][y]=1;
}
else
{
mapp[x][y]=2;
}
if(check_all(x,y))
{
flag=i;
}
}
if(!flag) puts("Tie");
else
{
if(flag&1) printf("A ");
else printf("B ");
printf("%d\n",flag);
}
return 0;
}
凉宫春日的忧郁
取对数…..
#include <bits/stdc++.h>
const double eps=1e-6;
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
double n,m;
cin>>n>>m;
double a=1,b=0;
a=m*log10(n);
for(int i=1; i<=m; ++i)
{
b+=log10(i);
}
if(a-b>=eps)
{
puts("No");
}
else puts("Yes");
}
return 0;
}
Back and Forth
想练一下DFS 结果题意被别人误导…..
#include <bits/stdc++.h>
const double eps=1e-6;
using namespace std;
int a[12],b[12],ans;
int tmp;
map<int,int>mp;
int sum;
void dfs(int now,int p,int pre){
if(now==1){
tmp=ans;
tmp-=a[p];
b[11]=a[p];
a[p]=0;
for(int j=1;j<=11;++j){
if(b[j])dfs(2,j,p);
}
a[p]=b[11];
}
if(now==2){
tmp+=b[p];
a[pre]=b[p];
b[p]=0;
for(int i=1;i<=10;++i){
if(a[i])dfs(3,i,p);
}
b[p]=a[pre];
tmp-=b[p];
}
if(now==3){
tmp-=a[p];
b[pre]=a[p];
a[p]=0;
for(int i=1;i<=11;++i){
if(b[i])dfs(4,i,p);
}
a[p]=b[pre];
tmp+=a[p];
}
if(now==4){
if(!mp[tmp+b[p]]){
mp[tmp+b[p]]=1;
sum++;
}
}
}
int main(){
for(int i=1;i<=10;++i){
scanf("%d",&a[i]);
}
ans=1000;
for(int i=1;i<=10;++i){
scanf("%d",&b[i]);
}
for(int i=1;i<=10;++i){
dfs(1,i,0);
}
printf("%d",sum);
return 0;
}
[DP]烤乐滋喝汤
一个很简单的DP．就是有一种情况他可能前面的都不管然后直接下药没考虑到．
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define met(a,x) memset(a,x,sizeof(a))
using namespace std;
const int maxn=1e5+7;
ll dp[maxn][2];
const int inf=0x3f3f3f3f;
int main()
{
ll n,m;
scanf("%lld%lld",&n,&m);
ll ans=-inf;ll s;
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; ++i){
scanf("%lld",&s);
if(i==1){
dp[i][0]=s;
dp[i][1]=max(dp[i-1][0]+m,m);
}
else{
dp[i][0]=max(s,dp[i-1][0]+s);
dp[i][1]=max(max(dp[i-1][0]+m,dp[i-1][1]+s),m);
}
ans=max(ans,dp[i][1]);
}
printf("%lld\n",ans);
return 0;
}
[取模运算]阿卡吃馅饼
一直想着怎么把数弄得很大，忘记取摸这个操作
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+7;
ll qpow(ll a,ll n,ll mod){
ll res=1;
while(n){
if(n&1){
res*=a;
res%=mod;
}
n>>=1;
a=(a*a)%mod;
}
return res;
}
int main(){
int n;scanf("%d",&n);
while(n--) {
int t, r;
scanf("%d%d", &t, &r);
int ans=0,i;
for(i=0;i<=1000;++i){
ans=(ans+qpow(10,i,r)*t%r)%r;
if(ans==0) break;
}
if(i==1001){
puts("GG");
}
else printf("%d\n",i);
}
}
[求回文串个数]大战幻想珠
两种情况
一个是从奇数出发，一个是从偶数出发
当出现?直接相等就好
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define ull unsigned long long
#define mp make_pair
#define met(a,x) memset(a,x,sizeof(a))
using namespace std;
const int maxn=1e5+7;
string s;
int n;
ll gao(){
ll ans = 0;
for (register int i=0; i<n;++i){
for (register int j=0; i+ j <n && i-j>=0 ; ++j){
if(s[i-j]==s[i+j]||s[i-j]=='?'||s[i+j]=='?')
ans++;
else break;
}
for (register int j=0; i + j <n && i-1-j>=0; ++j){
if(s[i-1-j]==s[i+j]||s[i-1-j]=='?'||s[i+j]=='?')
ans++;
else break;
}
}
return ans;
}
int main(){
cin>>n;cin>>s;
cout<<gao()<<endl;
return 0;
}
[暴力枚举]烤乐滋打虎
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define met(a,x) memset(a,x,sizeof(a))
using namespace std;
int s[101];
int d[101][101];
const int inf=0x3f3f3f3f;
int main()
{
int n;
scanf("%d",&n);
for(int i=1; i<=n; ++i)
{
scanf("%d",&s[i]);
}
for(int i=2; i<=n; ++i)
{
scanf("%d",&d[i][i-1]);
d[i-1][i]=d[i][i-1];
}
int ans=inf,tmp;
for(int i=1; i<=n; ++i)
{
int t=0;
tmp=0;
if(i!=n){
for(int j=i; j<=n; ++j){
tmp+=s[j]+t;
t+=d[j][j+1];
}
int p=i-1;
t*=2;
t+=d[p][i];
for(int j=p; j>=1; --j){
tmp+=s[j]+t;
t+=d[j][j-1];
}
ans=min(ans,tmp);
//cout<<ans<<" "<<i<<endl;
}
if(i!=1){
t=0;
tmp=0;
for(int j=i; j>=1; --j){
tmp+=s[j]+t;
t+=d[j][j-1];
}
t*=2;
t+=d[i][i+1];
for(int j=i+1; j<=n; ++j){
tmp+=s[j]+t;
t+=d[j][j+1];
}
ans=min(ans,tmp);
//cout<<ans<<" "<<i<<endl;
}
}
printf("%d\n",ans);
return 0;
}
旅程
先删掉一条边（赋值为INF）
跑FLOYD 记录询问 从后往前
遇到删边操作则枚举起点和终点\(n^2\)暴力更新答案
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=205;
int d[maxn][maxn];
int dis[maxn][maxn];
int n,m;
void floyd(){
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
struct node{
int u,v,op,val;
}s[100000+1];
void gao(int k){
int u=s[k].u;
int v=s[k].v;
int val=min(d[u][v],dis[u][v]);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
d[i][j]=min(d[i][j],d[i][u]+val+d[v][j]);
}
}
}
int vis[maxn][maxn];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
scanf("%d",&dis[i][j]);
d[i][j]=dis[i][j];
}
}
for(int i=1;i<=m;++i){
scanf("%d%d%d",&s[i].op,&s[i].u,&s[i].v);
if(s[i].op==1){
s[i].val=d[s[i].u][s[i].v];
d[s[i].u][s[i].v]=1e9;
vis[s[i].u][s[i].v]++;
}
}
floyd();
vector<int>vt;
for(int i=m;i>=1;--i){
if(s[i].op==2){
vt.push_back(d[s[i].u][s[i].v]);
}
else {
--vis[s[i].u][s[i].v];
if(!vis[s[i].u][s[i].v]){
gao(i);
}
}
}
int len=(int)vt.size();
for(int i=len-1;i>=0;--i){
if(vt[i]>=1e9) puts("-1");
else printf("%d\n",vt[i]);
}
return 0;
}子序列
数组数组求逆序数模板题
记住相同数的处理和相同和离散化
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
const int maxn=2e5+7;
ll c[maxn];
const int mod=1e9+7;
int lowbit(int i) {return i&(-i);}
ll pre_min[maxn],pre_max[maxn];
ll las_min[maxn],las_max[maxn];
int num[maxn];
int b[maxn];
ll sum(int x){
ll res=0;
for(int i=x;i>0;i-=lowbit(i)){
res+=c[i];
}
return res;
}
void add(int x,ll val){
for (int i =x; i <=n ; i+=lowbit(i)) {
c[i]+=val;
}
}
struct node{
ll val;
int id;
}s[maxn];
bool cmp(node a,node b){
if(a.val==b.val) return a.id<b.id;
return a.val<b.val;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&s[i].val);
c[i]=0;
s[i].id=i;
}
sort(s+1,s+1+n,cmp);
b[s[1].id]=1;
for(int i=2;i<=n;++i){
if(s[i].val!=s[i-1].val)b[s[i].id]=b[s[i-1].id]+1;
else if(s[i].val==s[i-1].val)b[s[i].id]=b[s[i-1].id];
}
for(int i=1;i<=n;++i){
add(b[i],1);
pre_max[i]=i-sum(b[i]);
pre_min[i]=(i-1-num[b[i]])-pre_max[i];
num[b[i]]++;
}
reverse(b+1,b+1+n);
memset(c,0,sizeof(c));
memset(num,0,sizeof(num));
for(int i=1;i<=n;++i){
add(b[i],1);
las_max[n-i+1]=sum(n)-sum(b[i]);
las_min[n-i+1]=(i-1-num[b[i]])-las_max[n-i+1];
num[b[i]]++;
}
ll ans=0;
for(int i=2;i<n;++i){
ans=(ans+pre_max[i]*las_min[i]%mod)%mod;
ans=(ans+pre_min[i]*las_max[i]%mod)%mod;
// cout<<i<<" "<<pre_max[i]<<" "<<las_min[i]<<endl;
// cout<<i<<" "<<pre_min[i]<<" "<<las_max[i]<<endl;
}
printf("%lld\n",ans);
return 0;
}