考前做题笔记
[KDOI-10]商店砍价
考虑dp，钦定全用操作 \(1\)，容易由 \(v_i\le 10^5\) 发现只有剩下的数位小于 \(6\) 时用操作 \(2\) 才更优。于是我们设 \(f_{i,j}\) 为考虑完第 \(i\) 位剩下 \(j\) 个数用操作 \(2\) 能减小的最大代价，并从高位向低位考虑。
转移方程很显然，选或不选用操作 \(2\) 能减小的代价取最大值，对于数位 \(x\) 剩下 \(j\) 位，因为是从低到高枚举用操作 \(2\) 即保留这一位的代价为 \(x\times 10^{j-1}\)。所以转移方程为 $$f_{i,j}=\max(f_{i+1,j},f_{i+1,j-1}+v_i-a_i\times 10^{j-1})$$ \(a_i\) 为输入数从左向右数第 \(i\) 位。
Code:
#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define int long long
#define ull unsigned long long
#define fst first
#define snd second
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-6;
inline bool pts(char ch){return ch>=48&&ch<=57;}
inline int read(){
bool f=0;int x=0;char ch;
ch=gt();
while(!pts(ch)&&ch!=EOF){if(ch=='-')f=1;ch=gt();}
while(pts(ch)){x*=10;x+=(ch-48);ch=gt();}
if(f)return -x;
else return x;
}
template<class T>
inline void print(T x){
char s[114];
int top=0;
if(x<0)pt('-');
do{
top++;
if(x>=0)s[top]=(x%10)+48;
else s[top]=(-(x%10)+48);
x/=10;
}while(x);
while(top){pt(s[top]);top--;}
}
int f[100005][10];
int v[10];
//|n|>5时1一定优，设f[i][j]为考虑到第i位利用策略二答案减小的值
void solve(){
memset(f,-1,sizeof(f));
string s;
cin>>s;
int len=s.size();
s=' '+s;
int sum=0;
for(int i=1;i<=9;i++)v[i]=read();
f[len+1][0]=0;
for(int i=len;i>=1;i--){
sum+=v[s[i]-'0'];
f[i][0]=f[i+1][0];
for(int j=1;j<=5;j++){
f[i][j]=max(f[i][j],f[i+1][j]);
f[i][j]=max(f[i+1][j],f[i+1][j-1]+v[s[i]-'0']-(s[i]-'0')*(int)powl(10,j-1));
}
}
int maxn=-1;
for(int j=1;j<=5;j++)
maxn=max(maxn,f[1][j]);
cout<<min(sum,sum-maxn)<<'\n';
}
signed main(){
int c=read(),T=read();
while(T--)solve();
return 0;
}
打字练习
把范文和输入分别读入，读入时用 getline，然后把每行字符串处理掉退格键加入到 vector 中方便比较，记正确的字符数为 \(cnt\)，答案即为 \(cnt\times 60\div t+0.5\)。
坑点：范文也有退格键，处理退格时注意写法。
Code：
#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define int long long
#define ull unsigned long long
#define fst first
#define snd second
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-6;
inline bool pts(char ch){return ch>=48&&ch<=57;}
inline int read(){
bool f=0;int x=0;char ch;
ch=gt();
while(!pts(ch)&&ch!=EOF){if(ch=='-')f=1;ch=gt();}
while(pts(ch)){x*=10;x+=(ch-48);ch=gt();}
if(f)return -x;
else return x;
}
template<class T>
inline void print(T x){
char s[114];
int top=0;
if(x<0)pt('-');
do{
top++;
if(x>=0)s[top]=(x%10)+48;
else s[top]=(-(x%10)+48);
x/=10;
}while(x);
while(top){pt(s[top]);top--;}
}
string fw[10005];
string sr[10005];
vector<char>v1[10005],v2[10005];
signed main(){
int cnt=0;
while(true){
cnt++;
getline(cin,fw[cnt]);
if(fw[cnt]=="EOF")break;
for(char c:fw[cnt]){
if(c!='<')v1[cnt].push_back(c);
else if(c=='<'&&v1[cnt].size()>0)v1[cnt].pop_back();//这两个if else顺序是坑点
}
}
int tnc=0;
while(true){
tnc++;
getline(cin,sr[tnc]);
if(sr[tnc]=="EOF")break;
for(char c:sr[tnc]){
if(c!='<')v2[tnc].push_back(c);
else if(c=='<'&&v2[tnc].size()>0)v2[tnc].pop_back();
}
}
int ans=0;
for(int i=1;i<=min(cnt,tnc);i++)
for(int j=0;j<min(v2[i].size(),v1[i].size());j++)
if(v1[i][j]==v2[i][j])ans++;
//cout<<(char)v1[i][j]<<' '<<(char)v2[i][j]<<'\n';
int T=read();
cout<<(int)(1.0*ans/T*60.0+0.5);
return 0;
}
「Daily OI Round 3」Tower
题目中的 \(e\) 实际上就是以 \((i,j)\) 为中心，在 \(A\) 国领地内的正方形的边长的最大值。
第一问是简单的，直接利用二维前缀和 \(O(n^3)\) 枚举即可。
第二问我们考虑求每个为平地的点对答案的贡献。假设点 \(B\) 在以 \(A\) 为中心的某个合法正方形的边缘，我们记点 \(A\) 与点 \(B\) 的 A距离 为 \(d\)，如果 \(B\) 变成山地，那么以 \(A\) 为中心的 \(e\) 会从 \(k\) 变为 \(k-1\)，所以它对答案的贡献会从 \(k^2\) 变为 \((k-1)^2\)，我们把原枚举到的正方形内所有点的贡献都减去 \(2k-1\) 即可，这一步可以用二维差分来做。
最终实现时间度为 \(O(n^3)\)。
Code：
#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define int long long
#define ull unsigned long long
#define fst first
#define snd second
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-6;
inline bool pts(char ch){return ch>=48&&ch<=57;}
inline int read(){
bool f=0;int x=0;char ch;
ch=gt();
while(!pts(ch)&&ch!=EOF){if(ch=='-')f=1;ch=gt();}
while(pts(ch)){x*=10;x+=(ch-48);ch=gt();}
if(f)return -x;
else return x;
}
template<class T>
inline void print(T x){
char s[114];
int top=0;
if(x<0)pt('-');
do{
top++;
if(x>=0)s[top]=(x%10)+48;
else s[top]=(-(x%10)+48);
x/=10;
}while(x);
while(top){pt(s[top]);top--;}
}
int a[605][605];
int sum[605][605];
int df[605][605];
void update(int x1,int y1,int x2,int y2,int v){
df[x1][y1]+=v;
df[x2+1][y1]-=v;
df[x1][y2+1]-=v;
df[x2+1][y2+1]+=v;
}
int getsum(int x1,int y1,int x2,int y2){
return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}
int ans=0;
signed main(){
int n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char ch;
cin>>ch;
if(ch=='.')a[i][j]=0;
else a[i][j]=1;
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
update(i,j,i,j,a[i][j]);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int e=0;
while(i+e<=n&&j+e<=m&&i-e>=1&&j-e>=1){
if(getsum(i-e,j-e,i+e,j+e))break;
e++;
}
ans+=e*e;
e=0;
while(i+e<=n&&j+e<=m&&i-e>=1&&j-e>=1){
if(getsum(i-e,j-e,i+e,j+e))break;
update(i-e,j-e,i+e,j+e,-(2*e+1));
e++;
}
}
}
cout<<ans<<'\n';
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
df[i][j]+=df[i-1][j]+df[i][j-1]-df[i-1][j-1];
if(a[i][j])cout<<-1<<' ';
else cout<<ans+df[i][j]<<' ';
}
cout<<'\n';
}
return 0;
}
[GXOI/GZOI2019] 旅行者
本题将单源最短路拓展到了多源最短路径上。
暴力是显然的，考虑优化。
跑两遍最短路，第一遍建图表示从兴趣城市出发到每个点的最短路 \(dist\) 和 \(st_i\) 表示到 \(i\) 最短路是从哪里来的；第二遍建反图表示从每个点出发到兴趣城市的最短路 \(tsid\) 和 \(ed_i\) 表示从 \(i\) 出发的最短路走到了哪。
求完之后对每条边 \((s,e,d)\) 考虑，如果 \(st_s=ed_e\)，说明在环上，忽略；否则维护答案（将答案与 \(dist_u+tsid_v+d\) 取最小值），可证明这一定是最短路。
注意将初始值开大点，如 \(10^18\)。
Code：
#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define int long long
#define ull unsigned long long
#define fst first
#define snd second
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-6;
inline bool pts(char ch){return ch>=48&&ch<=57;}
inline int read(){
bool f=0;int x=0;char ch;
ch=gt();
while(!pts(ch)&&ch!=EOF){if(ch=='-')f=1;ch=gt();}
while(pts(ch)){x*=10;x+=(ch-48);ch=gt();}
if(f)return -x;
else return x;
}
template<class T>
inline void print(T x){
char s[114];
int top=0;
if(x<0)pt('-');
do{
top++;
if(x>=0)s[top]=(x%10)+48;
else s[top]=(-(x%10)+48);
x/=10;
}while(x);
while(top){pt(s[top]);top--;}
}
const int MAXN=5e5+5;
struct Edge{
int s,e,d;
}edge[MAXN];
int n,m,k;
int dist[MAXN];
int tsid[MAXN];
bool vis[MAXN];
int st1[MAXN],ed2[MAXN];//st1_i到i最短路的兴趣城市，ed2_i到i到哪个兴趣城市
vector<pii>z[MAXN];
priority_queue<pii,vector<pii>,greater<pii> >h;
void add_edge(int s,int e,int d){
z[s].emplace_back(e,d);
}
vector<pii>g[MAXN];
void Add_Edge(int s,int e,int d){
g[s].emplace_back(e,d);
}
int c[MAXN];
void dijkstra1(){
while(h.size()){
int p=h.top().second;
h.pop();
if(vis[p])continue;
vis[p]=true;
for(int j=0;j<z[p].size();j++){
int q=z[p][j].first;
int d=z[p][j].second;
if(dist[q]>dist[p]+d){
dist[q]=dist[p]+d;
st1[q]=st1[p];
h.push(make_pair(dist[q],q));
}
}
}
}
void dijkstra2(){
while(h.size()){
int p=h.top().second;
h.pop();
if(vis[p])continue;
vis[p]=true;
for(int j=0;j<g[p].size();j++){
int q=g[p][j].first;
int d=g[p][j].second;
if(tsid[q]>tsid[p]+d){
tsid[q]=tsid[p]+d;
ed2[q]=ed2[p];
h.push(make_pair(tsid[q],q));
}
}
}
}
void solve(){
n=read(),m=read(),k=read();
//cout<<n<<' '<<m<<' '<<k<<'\n';
for(int i=1;i<=m;i++){
edge[i].s=read(),edge[i].e=read(),edge[i].d=read();
add_edge(edge[i].s,edge[i].e,edge[i].d);
Add_Edge(edge[i].e,edge[i].s,edge[i].d);
}
for(int i=1;i<=k;i++)c[i]=read();
for(int i=1;i<=n;i++)dist[i]=1e18;
memset(vis,false,sizeof(vis));
for(int i=1;i<=k;i++)h.push(make_pair(0,c[i])),dist[c[i]]=0,st1[c[i]]=c[i];
dijkstra1();
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)tsid[i]=1e18;
for(int i=1;i<=k;i++)h.push(make_pair(0,c[i])),tsid[c[i]]=0,ed2[c[i]]=c[i];
dijkstra2();
int ans=1e18;
for(int i=1;i<=m;i++){
if(st1[edge[i].s]==ed2[edge[i].e]||!st1[edge[i].s]||!ed2[edge[i].e])continue;
ans=min(ans,dist[edge[i].s]+tsid[edge[i].e]+edge[i].d);
}
cout<<ans<<'\n';
for(int i=0;i<=n+1;i++)z[i].clear(),g[i].clear();
}
signed main(){
int T=read();
while(T--)solve();
return 0;
}
[ABC007D]Small Multiple
每一个数都是可以由 \(1\) 通过 \(\times 10\) 或 \(+1\) 得出来的，容易发现进行前者完的数位和相比原数不变，进行后者完则数位和比原数大 \(1\)。于是我们将原问题转化为图论问题，在 \(\bmod k\) 意义下进行求解，我们把 \(1\sim k-1\) 每一个数看成点，向 \(i\times 10\) 连一条权值为 \(0\) 的边，向 \(i+1\) 连一条权值为 \(1\) 的边，然后从 \(1\) 开始跑最短路，因为是模 \(k\) 意义下进行的计算，所以最后答案为 \(dis_0+1\)。
Code：
#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define int long long
#define ull unsigned long long
#define fst first
#define snd second
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-6;
inline bool pts(char ch){return ch>=48&&ch<=57;}
inline int read(){
bool f=0;int x=0;char ch;
ch=gt();
while(!pts(ch)&&ch!=EOF){if(ch=='-')f=1;ch=gt();}
while(pts(ch)){x*=10;x+=(ch-48);ch=gt();}
if(f)return -x;
else return x;
}
template<class T>
inline void print(T x){
char s[114];
int top=0;
if(x<0)pt('-');
do{
top++;
if(x>=0)s[top]=(x%10)+48;
else s[top]=(-(x%10)+48);
x/=10;
}while(x);
while(top){pt(s[top]);top--;}
}
const int MAXN=1e6+5;
int k;
int dist[MAXN];
bool vis[MAXN];
vector<pii>z[MAXN];
priority_queue<pii,vector<pii>,greater<pii> >h;
void add_edge(int s,int e,int d){
z[s].emplace_back(e,d);
}
void dijkstra(int s){
memset(dist,0x3f,sizeof(dist));
dist[s]=0;
h.push(make_pair(0,s));
while(h.size()){
int p=h.top().second;
h.pop();
if(vis[p])continue;
vis[p]=true;
for(int j=0;j<z[p].size();j++){
int q=z[p][j].first;
int d=z[p][j].second;
if(dist[q]>dist[p]+d){
dist[q]=dist[p]+d;
h.push(make_pair(dist[q],q));
}
}
}
}
signed main(){
k=read();
for(int i=0;i<=k-1;i++){
add_edge(i,i*10%k,0);
add_edge(i,(i+1)%k,1);
}
dijkstra(1);
cout<<dist[0]+1;
return 0;
}