cf611e
简单题，三个火枪手分别有a，b，c 的攻击，打怪，每个怪有生命值，每回合三个火枪手各选一个怪打，怪只有一回合里被各个火枪手打的累计伤害大于等于生命值才会死。求最少多少回合打怪
#include<bits/stdc++.h>#define FOR(i,s,t) for(int i=s;i<=t;++i)#define REP(i,t,s) for(int i=t;i>=s;--i)#define RESET(a) memset(a,0,sizeof a)using namespace std;typedef long long LL;multiset<int,greater<int> > st;int n,a,b,c;int main() {cin>>n>>a>>b>>c;int x;FOR(i,1,n) cin>>x,st.insert(x);if(a>b) swap(a,b);if(a>c) swap(a,c);if(b>c) swap(b,c);if(*st.begin()>a+b+c) return cout<<-1,0;int ans=0;while(!st.empty()) {++ans;auto it=st.begin();int w=*it;st.erase(it);if(st.empty()) break;if(w>b+c) continue;if(w>a+c) {it=st.lower_bound(a);if(it!=st.end()) st.erase(it);continue;}if(w>a+b&&w>c) {it=st.lower_bound(b);if(it!=st.end()) st.erase(it);continue;}if(w>c&&w<=a+b) {it=st.lower_bound(c);if(it!=st.end()) st.erase(it);continue;}if(w>b&&w<=c) {auto it1=st.lower_bound(b);if(it1!=st.end()) {int t=*it1;st.erase(it1);auto it2=st.lower_bound(a);if(it2!=st.end()) {st.erase(it2);continue;}st.insert(t);}it=st.lower_bound(a+b);if(it!=st.end()) st.erase(it);continue;}if(w>a) {it=st.lower_bound(c);if(it!=st.end()) st.erase(it);it=st.lower_bound(a);if(it!=st.end()) st.erase(it);continue;}if(1) {it=st.lower_bound(c);if(it!=st.end()) st.erase(it);it=st.lower_bound(b);if(it!=st.end()) st.erase(it);continue;}}cout<<ans;}
cf873f
统计没有被block的所有串的总长。sam。
#include<bits/stdc++.h>#define FOR(i,s,t) for(int i=s;i<=t;++i)#define REP(i,t,s) for(int i=t;i>=s;--i)#define RESET(a) memset(a,0,sizeof a)using namespace std;typedef long long LL;const int N=4e5+5;int n,c[N][26],fa[N],l[N],ed[N],np=1,cnt=1;int cc[N],aa[N];char ss[N],so[N];void ins(int x,int o) {int p=np; np=++cnt,l[np]=l[p]+1,ed[np]=o;for(;p&&!c[p][x];p=fa[p]) c[p][x]=np;if(!p) fa[np]=1;else {int q=c[p][x];if(l[q]==l[p]+1) fa[np]=q;else {int nq=++cnt; l[nq]=l[p]+1;memcpy(c[nq],c[q],104);fa[nq]=fa[q],fa[q]=fa[np]=nq;for(;c[p][x]==q;p=fa[p]) c[p][x]=nq;}}}int main() {scanf("%d%s%s",&n,ss,so);FOR(i,0,n-1) ins(ss[i]-'a',so[i]!='1');FOR(i,1,cnt) ++cc[l[i]];FOR(i,1,cnt) cc[i]+=cc[i-1];FOR(i,1,cnt) aa[cc[l[i]]--]=i;REP(i,cnt,1) ed[fa[aa[i]]]+=ed[aa[i]];LL ans=0;FOR(i,1,cnt) ans=max(ans,1LL*ed[i]*l[i]);printf("%lld\n",ans);}
cf264d
1e6的2个RGB串中各有一个棋子初始在串首，每次同时对两个棋子发出一个颜色指令R/G/B，如果棋子所在的格子与指令的颜色不同，就前进一格。求有多少棋子位置pair（p1,p2)在所有可能的移动中可以产生。
要打表！ 发现1e6*1e6的表中，所有的答案被两条递增线包围，且其中有且仅有(i-1,j)和(i,j-1)都是x,y同时加的，也就是在网格上斜加的。
//完全贺题！#include<bits/stdc++.h>#define RG register#define R RG intusing namespace std;const int N=1e6+9;char s[N],t[N];int f[N][8];int main(){R n=0,m=0,x,y,l=0,r=0;RG long long ans=0;scanf("%s%s",s,t);for(n=0;s[n];++n)s[n]%=3;//只是凑巧发现RBG%3的余数不一样for(m=0;t[m];++m)t[m]%=3;for(x=1;x<n;++x){memcpy(f[x],f[x-1],32);//前缀和if(s[x-1]!=s[x])++f[x][(s[x-1]>s[x])*4+s[x-1]+s[x]];}memcpy(f[n],f[n-1],32);for(y=0;y<m;++y){if(y&&t[y-1]!=t[y]){//注意边界x=(t[y-1]<t[y])*4+t[y-1]+t[y];ans-=f[r][x]-f[l][x];}while(r<n&&s[r]!=t[y])++r;ans+=r-l+1-(r==n);//同样注意边界if(r<n)++r;if(l<r&&s[l]==t[y])++l;}cout<<ans<<endl;return 0;}
cf1320d
自然溢出失败，双哈希写的翔死，最后发现是算法假了。。
要用0的间隔的奇偶来判断，而不是1的繁琐操作后的结果
cf1438c
一个矩阵， 每个数可以+1，选择一些数+1，使相邻的格子的数奇偶性不同
i+j奇的奇，偶的偶
#include<bits/stdc++.h>#define FOR(i,s,t) for(int i=s;i<=t;++i)#define REP(i,t,s) for(int i=t;i>=s;--i)#define mem(a,x) memset(a,x,sizeof a)using namespace std;typedef long long ll;int a[111][111];int main() {int t;cin>>t;while(t--) {int n,m;cin>>n>>m;FOR(i,1,n) FOR(j,1,m) {cin>>a[i][j];if((a[i][j]^i+j)&1) ++a[i][j];}FOR(i,1,n) {FOR(j,1,m) cout<<a[i][j]<<' ';cout<<endl;}}}
hdu6833
莫比乌斯反演要注意加了条件d|i之后∑i=1n\sum_{i=1}^n∑i=1n要变的
hdu3062
复习了一下2-sat。。然而只打了tarjan的版本，暴搜找字典序最小的就不管了叭
#include<bits/stdc++.h>#define REP(i,t,s) for(int i=t;i>=s;--i)#define mem(a,x) memset(a,x,sizeof a)using namespace std;const int N=4005;int n,m,dfn[N],low[N],col[N],inq[N],Q[N],num,top,cnt,a1,a2,c1,c2;vector<int> e[N];void tarjan(int u) {dfn[u]=low[u]=++num,Q[++top]=u,inq[u]=1;for(auto v:e[u])if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);else if(inq[v]) low[u]=min(low[u],dfn[v]);if(dfn[u]==low[u]&&++cnt)do col[Q[top]]=cnt,inq[Q[top]]=0; while(u!=Q[top--]);}int main() {while(~scanf("%d%d",&n,&m)) {REP(i,2*n-1,0) e[i].clear(); mem(dfn,0),num=top=cnt=0;while(m--) {scanf("%d%d%d%d",&a1,&a2,&c1,&c2);e[a1*2+c1].push_back(a2*2+1-c2);e[a2*2+c2].push_back(a1*2+1-c1);}REP(i,2*n-1,0) if(!dfn[i]) tarjan(i);REP(i,n-1,0) if(col[i*2]==col[i*2+1]) {puts("NO"); c1=2077;break;}if(c1!=2077) puts("YES");}}
cf1187g
分层图费用流，不知道确切层数，乱建出超大的图，调了半天，发现一个是数组大小开错一个是n和k弄错
#pragma GCC optimize("inline",3)#include<bits/stdc++.h>#define FOR(i,s,t) for(int i=s;i<=t;++i)#define REP(i,t,s) for(int i=t;i>=s;--i)#define mem(a,x) memset(a,x,sizeof a)using namespace std;typedef long long ll;const int B=177,N=50*(B+1)+10,M=N*300,inf=1e8;int n,m,K,C,D,S,T,tot=1;int hd[N],dis[N],pre[N],inq[N];struct edge {int nx,to,fl,cs;} e[M];void ad(int a,int b,int c,int d) {e[++tot]={hd[a],b,c,d};hd[a]=tot;}void add(int a,int b,int c,int d) {ad(a,b,c,d),ad(b,a,0,-d);}int spfa() {mem(dis,63),dis[S]=0; queue<int> Q; Q.push(S);while(!Q.empty()) {int u=Q.front(); Q.pop(); inq[u]=0;for(int i=hd[u];i;i=e[i].nx) {int v=e[i].to;if(e[i].fl && dis[v] > dis[u]+e[i].cs) {dis[v]=dis[u]+e[i].cs;pre[v]=i;if(!inq[v]) inq[v]=1,Q.push(v);}}}return dis[T]<inf;}int mcmf() {int cst=0,flw=0;while(spfa()) {int f=inf;for(int i=pre[T];i;i=pre[e[i^1].to]) f=min(f,e[i].fl);flw+=f;for(int i=pre[T];i;i=pre[e[i^1].to]) {cst+=f*e[i].cs;e[i].fl-=f;e[i^1].fl+=f;}}return cst;}int main() {ios::sync_with_stdio(0);int x,y;cin>>n>>m>>K>>C>>D;S=n*(B+1)+1,T=n*(B+1)+2;FOR(i,1,K) cin>>x,add(S,x,1,0);FOR(i,1,m) {cin>>x>>y;FOR(t,1,B) REP(w,K,1) {add(n*(t-1)+x,n*t+y,1,C+D*(2*w-1));add(n*(t-1)+y,n*t+x,1,C+D*(2*w-1));}}FOR(u,1,n) FOR(t,1,B) REP(w,K,1) {add(n*(t-1)+u,n*t+u,1,C);}FOR(t,1,B) add(n*t+1,T,inf,0);cout<<mcmf();}
cf1051e
要求lcp的简单dp，搞了个双模哈希，又搞了半天，发现是dp的0每判条件
#pragma GCC optimize("inline",3)#include<bits/stdc++.h>#define FOR(i,s,t) for(int i=s;i<=t;++i)#define REP(i,t,s) for(int i=t;i>=s;--i)#define mem(a,x) memset(a,x,sizeof a)using namespace std;typedef long long ll;const int N=1e6+6,M=998244353,HX=1e9+7,HY=1e9+9;struct pr {int x,y;pr operator+(pr o) {return {(x+o.x)%HX,(y+o.y)%HY}; }pr operator-(pr o) {return {(x-o.x+HX)%HX,(y-o.y+HY)%HY}; }pr operator*(pr o) {return {1ll*x*o.x%HX,1ll*y*o.y%HY}; }bool operator==(pr o) {return x==o.x && y==o.y; }} ha[N],hl[N],hr[N],hs[N],SE={48271,48271};char sa[N],sl[N],sr[N];int n,nl,nr,bit[N];void add(int p,int v) {for(;p<=n;p+=p&-p) (bit[p]+=v)%=M;}int qry(int p) {int re=0;for(;p;p-=p&-p) (re+=bit[p])%=M;return re;}int lcp(pr *a,pr *b,int d) {int l=0,r=d;while(l<r) {int mi=l+r+1>>1;if(a[mi]-hs[mi]*a[0] == b[mi]-hs[mi]*b[0]) l=mi;else r=mi-1;}return l;}int main() {scanf("%s%s%s",sa+1,sl+1,sr+1);n=strlen(sa+1);nl=strlen(sl+1);nr=strlen(sr+1);ha[0]=hl[0]=hr[0]=hs[0]={1,1};FOR(i,1,N-1) {hs[i]=hs[i-1]*SE;ha[i]=ha[i-1]*SE+(pr){sa[i],sa[i]};hl[i]=hl[i-1]*SE+(pr){sl[i],sl[i]};hr[i]=hr[i-1]*SE+(pr){sr[i],sr[i]};}FOR(i,1,n-nl+1) {int cur= i==1 ? 1 : qry(i-1);if(sa[i]=='0') {if(nl==1&&sl[1]=='0') {add(i,cur);add(i+1,-cur);}continue;}int ll=nl;{int t=lcp(ha+i-1,hl,nl);ll+=(t<nl && sa[i+t]<sl[t+1]);}int rr=min(nr,n-i+1);if(rr==nr){int t=lcp(ha+i-1,hr,nr);rr-=(t<nr && sa[i+t]>sr[t+1]);}if(ll<=rr) add(i+ll-1,cur),add(i+rr,-cur);}printf("%d\n",(qry(n)+M)%M);}
cf925d
看错题目的神题
//hehehehehehehehehhhhhhhhhhhhhhhhh#include<bits/stdc++.h>#define N 400000using namespace std;set<int>s[N];int bl[N],S[N],sz,n,m;void dfs(int x,int y){bl[x]=y;++sz;for(int z:s[x])if(z!=1&&!bl[z])dfs(z,y);}void dft(int x){S[x]=sz;for(int y:s[x])if(y!=1&&!S[y])dft(y);}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);s[x].insert(y);s[y].insert(x);}if(s[1].count(n))return printf("1\n1 %d\n",n),0;for(int x:s[1])if(s[x].count(n))return printf("2\n1 %d %d\n",x,n),0;for(int x:s[1])for(int y:s[x])if(s[y].count(n))return printf("3\n1 %d %d %d\n",x,y,n),0;for(int x:s[1])for(int y:s[x])if(y!=1&&!s[1].count(y))return printf("4\n1 %d %d 1 %d\n",x,y,n),0;if(!s[1].size())return puts("-1"),0;for(int x:s[1])if(!bl[x]){sz=0;dfs(x,x);dft(x);}int mn=n+10,mid=0;for(int x:s[1])if(S[x]!=s[x].size()){if(s[x].size()<mn){mn=s[x].size();mid=x;}}if(mid){puts("5");for(int y:s[mid])if(y!=1)for(int z:s[y])if(z!=1&&z!=mid&&!s[mid].count(z))return printf("1 %d %d %d %d %d\n",mid,y,z,mid,n),0;}puts("-1");return 0;}
cf840c
dp好题，不会
///icefox_zhx/article/details/77487281#include <bits/stdc++.h>#define N 305#define ll long longint const mod=1e9+7;int n,a[N],size[N],nn=0,f[N][N],C[N][N];//f[i][j]表示前i组，有j个相邻的同组 ll fact[N];bool vis[N];inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;}inline bool check(ll x){ll xx=sqrt(x);if(xx*xx==x) return 1;else return 0;}inline void calc(){//预处理组合数和阶乘 C[0][0]=1;for(int i=1;i<=n;++i){C[i][0]=1;for(int j=1;j<=i;++j)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}fact[0]=1;for(int i=1;i<=n;++i) fact[i]=(ll)fact[i-1]*i%mod;}int main(){// freopen("a.in","r",stdin);n=read();for(int i=1;i<=n;++i) a[i]=read();for(int i=1;i<=n;++i){if(vis[i]) continue;vis[i]=1;size[++nn]=1;for(int j=i+1;j<=n;++j)if(check((ll)a[i]*a[j])) vis[j]=1,size[nn]++;}calc();int tot=0;f[0][0]=1;for(int i=1;i<=nn;++i){for(int j=0;j<=tot;++j)//dp[i-1][j]for(int k=1;k<=size[i]&&k<=tot+1;++k)//把第i组分成k部分for(int D=0;D<=k&&D<=j;++D)//消掉D个连续的同组f[i][j-D+size[i]-k]=(f[i][j-D+size[i]-k]+(ll)f[i-1][j]*C[size[i]-1][k-1]%mod*C[j][D]%mod*C[tot+1-j][k-D])%mod;tot+=size[i];}ll ans=f[nn][0];for(int i=1;i<=nn;++i) ans=ans*fact[size[i]]%mod;//乘上排列总数 printf("%lld\n",ans);return 0;}
cf1363f
dp好题，不会
//heeeeeeeeeeeeeeeeeeeeeeeeeeeeee#include <bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define endl "\n"#define int long longconst int N = ;int n;string s, t;int suf[26][N], suf2[26][N];int cache[N][N];int dp(int i, int j){if(j == 0)return 0;int &ans = cache[i][j];if(ans != -1)return ans;ans = 2e9;if(i > 0){ans = 1 + dp(i - 1, j);if(s[i - 1] == t[j - 1])ans = min(ans, dp(i - 1, j - 1));}int ch = t[j - 1] - 'a';if(suf[ch][i + 1] - suf2[ch][j + 1] > 0)ans = min(ans, dp(i, j - 1));return ans;}int32_t main(){IOS;int tc;cin >> tc;while(tc--){cin >> n >> s >> t;for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)cache[i][j] = -1;for(int i = 0; i <= 25; i++)for(int j = 0; j <= n + 1; j++)suf[i][j] = suf2[i][j] = 0;for(int i = n; i >= 1; i--){for(int j = 0; j < 26; j++){suf[j][i] = suf[j][i + 1];suf2[j][i] = suf2[j][i + 1];}suf[s[i - 1] - 'a'][i]++;suf2[t[i - 1] - 'a'][i]++;}int ans = dp(n, n);if(ans > 1e9)ans = -1;cout << ans << endl;}return 0;}
cf1340d
想了好久想到思路，结果D-d~D 被我想成了0~d,看不出来，只好贺了
#include<bits/stdc++.h>#define FOR(i,s,t) for(int i=s;i<=t;++i)#define REP(i,t,s) for(int i=t;i>=s;--i)#define mem(a,x) memset(a,x,sizeof a)using namespace std;typedef long long ll;const int N=1e5+6;int n,D;vector<int> e[N];queue<pair<int,int> > ans;void dfs(int u,int f,int c) {ans.push({u,c});int d=e[u].size();int p=c;for(auto v:e[u]) if(v!=f) {if(p==D) p=D-d,ans.push({u,p});dfs(v,u,++p);}if(f&&p!=c-1) ans.push({u,c-1});if(f) ans.push({f,c});}int main() {scanf("%d",&n);FOR(i,1,n-1) {int x,y;scanf("%d%d",&x,&y);e[x].push_back(y);e[y].push_back(x);}if(n==1) return puts("1\n1 0"),0;FOR(i,1,n) D=max(D,(int)e[i].size());dfs(1,0,0);printf("%lld\n",ans.size());while(!ans.empty()) {auto t=ans.front(); ans.pop();printf("%d %d\n",t.first,t.second);}}
cf1301e
大前缀和，搞了一个二维st表代码密密麻麻
#include<bits/stdc++.h>#define FOR(i,s,t) for(int i=s;i<=t;++i)#define REP(i,t,s) for(int i=t;i>=s;--i)#define mem(a,x) memset(a,x,sizeof a)using namespace std;typedef long long ll;const int N=505,B=10,D[4][2]={{-1,-1},{-1,1},{1,-1},{1,1}};const int E[4][2]={{0,0},{0,1},{1,0},{1,1}};int n,m,q,ss[4][N][N],co[4][N][N],ra[N][N],st[B][N][B][N];char g[N][N];int ctoi(char c) {returnc=='R' ? 0 :(c=='G' ? 1 : (c=='Y' ? 2 : 3));}int full(int o,int i,int j,int x,int y) {if(i>x) swap(i,x);if(j>y) swap(j,y);--i,--j;return ss[o][x][y]-ss[o][x][j]-ss[o][i][y]+ss[o][i][j] == (x-i)*(y-j);}int qmax(int i,int j,int x,int y) {//cerr << "qmax_" << i << ' ' << j << ' ' << x << ' ' << y << endl;int d1=floor(log2(x-i+1));int d2=floor(log2(y-j+1));//cerr << " " << "d1_ " << d1 << " d2_ " << d2 << endl;return max(max(st[d1][i][d2][j],st[d1][x-(1<<d1)+1][d2][j]),max(st[d1][i][d2][y-(1<<d2)+1],st[d1][x-(1<<d1)+1][d2][y-(1<<d2)+1]));}int main() {scanf("%d%d%d",&n,&m,&q);FOR(i,1,n) {scanf("%s",g[i]+1);FOR(j,1,m) g[i][j]=ctoi(g[i][j]),ss[g[i][j]][i][j]=1;}FOR(o,0,3) FOR(i,1,n) FOR(j,1,m)ss[o][i][j]+=ss[o][i][j-1]+ss[o][i-1][j]-ss[o][i-1][j-1];FOR(o,0,3) FOR(i,1,n-1) FOR(j,1,m-1) {int l=1,r,x=i+E[o][0],y=j+E[o][1];if(o==0) r=min(i,j);if(o==1) r=min(i,m-j);if(o==2) r=min(n-i,j);if(o==3) r=min(n-i,m-j);while(l<r) {int mi=l+r+1>>1;if(full(o,x,y,x+D[o][0]*(mi-1),y+D[o][1]*(mi-1))) l=mi;else r=mi-1;}if(full(o,x,y,x,y)) co[o][i][j]=l;}FOR(i,1,n-1) FOR(j,1,m-1) ra[i][j]=min(min(co[0][i][j],co[1][i][j]),min(co[2][i][j],co[3][i][j]));FOR(i,1,n-1) FOR(j,1,m-1) st[0][i][0][j]=ra[i][j];for(int p=0;(1<<p)<n;++p)for(int i=1;i+(1<<p)-1<n;++i)for(int q=0;(1<<q)<m;++q) if(p||q)for(int j=1;j+(1<<q)-1<m;++j) {if(p) st[p][i][q][j]=max(st[p-1][i][q][j],st[p-1][i+(1<<p-1)][q][j]);else st[p][i][q][j]=max(st[p][i][q-1][j],st[p][i][q-1][j+(1<<q-1)]);//if(p==0&&i==1&&q==1&&j==1) puts("#######");}//FOR(i,1,n) {//FOR(j,1,m) printf("%3d",ra[i][j]);//puts("");//}//while(q--) {int i,j,x,y;scanf("%d%d%d%d",&i,&j,&x,&y);int l=0,r=min(x-i+1,y-j+1)/2;while(l<r) {int mi=l+r+1>>1;if(i+mi-1<=x-mi && j+mi-1<=y-mi&&qmax(i+mi-1,j+mi-1,x-mi,y-mi)>=mi) l=mi;else r=mi-1;}printf("%d\n",4*l*l);}}
如果觉得《记录4 最近贺题时做的题 cf611e cf873f cf264d cf1320d cf1438c hdu6833 hdu3602 cf1187g cf1051e cf925d cf840c etc》对你有帮助，请点赞、收藏，并留下你的观点哦！
