考前做题笔记

[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|>6时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<=6;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<=6;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\)。

坑点：范文也有退格键，处理退格时注意写法。

#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;
}