link
C-Minimization
枚举覆盖(1)的区间，两边的次数直接算
#include<bits/stdc++.h>
#define ll long long
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"
"
#define dbg3(x) cerr<<#x<<"
"
using namespace std;
#define reg register
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<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
const int MN=1e5+5;
int N,K,P;
int main()
{
N=read(),K=read();
reg int i,ans=N;
for(i=1;i<=N;++i) read()==1?P=i:0;
for(i=1;i<=K;++i)if(P>=i&&P+K-i<=N)
ans=min(ans,1+(P-i+K-2)/(K-1)+(N-P-K+i+K-2)/(K-1));
printf("%d
",ans);
}
D-Snuke Numbers
答案的序列是(1,2,3,4,5,6,7,8,9,19,29,39,..,99,199,299,399...)
发现每次的增量都是(10^{i})，所以每次比较一下(frac{now+10^i}{S(now+10^i)})和(frac{now+10^{i+1}}{S(now+10^{i+1})})
看下一个是加(10^i)还是(10^{i+1})
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
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<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
ll D[18],d,now=1;
ll get_now(ll p){ll r=0;for(;p;r+=p%10,p/=10);return r;}
int main()
{
D[0]=1;
for(int i=1;i<=17;++i) D[i]=D[i-1]*10ll;
int n=read();
while(n--)
{
printf("%lld
",now);
if((now+D[d])*get_now(now+2*D[d])>(now+D[d]*2)*get_now(now+D[d])) d++;
now+=D[d];
}
return 0;
}
E-Independence
考虑原图的返图，答案存在当且仅当它是一个二分图
将二分图的每个联通块黑色和白色的数量求出来，(dp)算出最后一个块的大小是否可以是(i)
对所有可行方案求出一个最小值即可
#include<bits/stdc++.h>
#define ll long long
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"
"
#define dbg3(x) cerr<<#x<<"
"
using namespace std;
#define reg register
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<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
const int MN=705;
int N,M;
bool G[MN][MN],vis[MN],col[MN],f[MN][MN];
int num[2][MN],T;
void dfs(int x)
{
++num[col[x]][T];vis[x]=true;reg int i;
for(i=1;i<=N;++i)if(i!=x&&!G[x][i])
{
if(!vis[i])col[i]=col[x]^1,dfs(i);
else if(col[i]==col[x]) {puts("-1");exit(0);}
}
}
int cal(int x,int y){return (x*(x-1)+y*(y-1))/2;}
int main()
{
N=read();M=read();
reg int i,j,x,y;
for(i=1;i<=M;++i) x=read(),y=read(),G[x][y]=G[y][x]=1;
for(i=1;i<=N;++i)if(!vis[i])++T,dfs(i);
f[0][0]=1;
for(i=0;i<T;++i)for(j=0;j<=N;++j)
f[i+1][j+num[0][i+1]]|=f[i][j],
f[i+1][j+num[1][i+1]]|=f[i][j];
int ans=MN*MN;
for(i=0;i<=N;++i)if(f[T][i])ans=min(ans,cal(i,N-i));
return 0*printf("%d
",ans);
}
F-Eating Symbols Hard
字符串(Hash)，求出全部操作后的字符串的哈希值，把它插入(map)
[hash=sum_{i=-1e9}^{1e9} A_i x^i
]
求出当前前缀操作后字符串的哈希值(num)，(ans+=map[num])
求出一段当前前缀操作后再执行总操作的哈希值，把它插入(map)
可以定义(num)是有(6)个元素的结构体，包含分别用(6)个底数求出的哈希值
#include<bits/stdc++.h>
#define ll long long
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"
"
#define dbg3(x) cerr<<#x<<"
"
using namespace std;
#define reg register
const int MN=250005;
int N;
char s[MN];
const int P=998244353;
int Add(int x,int y){return (x+y)%P;}
int Mul(int x,int y){return (1ll*x*y)%P;}
const int B[]={691,769,823,877,911,967},
inv[]={37560569,983965175,992179685,349442436,115055606,356147158};
struct node
{
int v[6];
int& operator [](int x){return v[x];}
bool operator <(const node o)const
{
for(int i=0;i<6;++i)if(v[i]!=o.v[i])return v[i]<o.v[i];
return false;
}
bool operator ==(const node o)const
{
for(int i=0;i<6;++i)if(v[i]!=o.v[i])return false;
return true;
}
}pre[MN],all;
std::map<node,int> Mp;
int pos[MN],nm[6][MN<<1],cal[MN];
node get(node x,node y,int p)
{
for(int j=0;j<6;++j)
x[j]=Add(x[j],Mul(y[j],nm[j][p]));
return x;
}
int main()
{
scanf("%d%s",&N,s+1);
reg int i,j,k;
for(j=0;j<6;++j)for(nm[j][MN]=i=1;i<=N;++i)
nm[j][i+MN]=Mul(nm[j][i-1+MN],B[j]),
nm[j][-i+MN]=Mul(nm[j][-i+1+MN],inv[j]);
for(k=j=0;j<6;++j,k=0)for(i=1;i<=N;++i)
{
switch(s[i])
{
case '<':--k;break;
case '>':++k;break;
case '+':all[j]=Add(all[j],nm[j][k+MN]);break;
case '-':all[j]=Add(all[j],P-nm[j][k+MN]);break;
}
pos[i]=k;pre[i][j]=all[j];
}
++Mp[all];
for(i=1;i<=N;++i)
cal[i]=Mp[pre[i]],
++Mp[get(pre[i],all,pos[i]+MN)];
ll ans=0;
for(i=1;i<=N;++i) ans+=cal[i];
return 0*printf("%lld
",ans);
}
Blog来自PaperCloud，未经允许，请勿转载，TKS！