杂题选做[1]

第一次发这种类型文章

好吧，其实是我刷题太少了，所以开始补了 $😅$

一些收获：（~~q779脑回路清奇，所以会想出很多乱七八糟的~~）

DP有个无后效性：某阶段的状态一旦确定，则此后过程的决策不再受此前各种状态及决策的影响
暴力也是可以剪枝的
$a_n=a_1+(n-1)d$

P1209 [USACO1.3]修理牛棚 Barn Repair

贪心。木板可以随便切，所以每次切间隔最大的。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1005)
int n,m,a[N],b[N],res;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> m >> n >> n;
    for(int i=1; i<=n; i++) cin >> a[i]; 
    sort(a+1,a+1+n); res=a[n]-a[1]+1;
    for(int i=1; i<n; i++) b[i]=a[i+1]-a[i]; sort(b+1,b+n);
    for(int i=1; i<=m-1&&i<n; i++) res-=b[n-i]-1; cout << res;
    return 0;
}

P1214 [USACO1.4]等差数列 Arithmetic Progressions

可以发现集合内的所有数至多有约 $2\times 10^4$ 个数

时限 5.00s

考虑 $O(nm^2)$ 暴力枚举+剪枝

事实上是跑不到这个上界的，所以跑得还蛮快

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
unordered_map<int,bool>mp;
int n,m,a[N],pos,cnt;
struct node{int a,b;}ans[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=0; i<=m; i++)
        for(int j=0; j<=m; j++)
            a[++pos]=i*i+j*j;
    sort(a+1,a+1+pos);
    pos=unique(a+1,a+1+pos)-a-1;
    for(int i=1; i<=pos; i++) mp[a[i]]=1;
    for(int i=1; i<=pos; i++)
        for(int j=i+1; j<=pos; j++)
        {
            int a1=a[i],d=a[j]-a[i],p=1;
            if(a1+(n-1)*d>a[pos])break;
            if(!mp[a1+(n-1)*d])continue;
            while(mp[a1+p*d])
            {
                if(p==n-1){ans[++cnt]={a1,d};break;}
                ++p;
            }
        }
    sort(ans+1,ans+1+cnt,[](node a,node b)
    {
        return a.b==b.b?a.a<b.a:a.b<b.b;
    });
    if(cnt==0)cout << "NONE";
    for(int i=1; i<=cnt; i++)
        cout << ans[i].a << " " << ans[i].b << endl;
    return 0;
}

P1465 [USACO2.2]序言页码 Preface Numbering

无聊的模拟题。基本思想就是，取模+模拟。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (25)
int n,i[20],v[20],x[20],l[20],c[20],d[20],m[20],A[20];
int ansi,ansv,ansx,ansl,ansc,ansd,ansm;
void init()
{
    A[1]=1;i[1]=1;
    A[2]=4;i[2]=1;v[2]=1;
    A[3]=5;v[3]=1;
    A[4]=9;i[4]=1;x[4]=1;
    A[5]=10;x[5]=1;
    A[6]=40;x[6]=1;l[6]=1;
    A[7]=50;l[7]=1;
    A[8]=90;x[8]=1;c[8]=1;
    A[9]=100;c[9]=1;
    A[10]=400;c[10]=1;d[10]=1;
    A[11]=500;d[11]=1;
    A[12]=900;c[12]=1;m[12]=1;
    A[13]=1000;m[13]=1;
}
void add(int u,int num)
{
    ansi+=i[u]*num;
    ansv+=v[u]*num;
    ansx+=x[u]*num;
    ansl+=l[u]*num;
    ansc+=c[u]*num;
    ansd+=d[u]*num;
    ansm+=m[u]*num;
    return;
}
signed main()
{
    scanf("%lld",&n);
    init();
    for(int k=1; k<=n; k++)
    {
        int tmp=k,now=13;
        while(tmp)
        {
            while(tmp<A[now])--now;
            add(now,tmp/A[now]);
            tmp%=A[now];
        }
    }
    if(ansi!=0) printf("I %lld\n",ansi);
    if(ansv!=0) printf("V %lld\n",ansv);
    if(ansx!=0) printf("X %lld\n",ansx);
    if(ansl!=0) printf("L %lld\n",ansl);
    if(ansc!=0) printf("C %lld\n",ansc);
    if(ansd!=0) printf("D %lld\n",ansd);
    if(ansm!=0) printf("M %lld\n",ansm);
    return 0;
}

P1461 [USACO2.1]海明码 Hamming Codes

枚举可能的数然后判断

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(105)
int n,b,d,a[N];
int count(int x)
{
    int res=0;
    for(;x;res+=x&1,x>>=1);
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> b >> d;
    for(int i=2; i<=n; i++)
        for(int now=a[i-1]; now<1<<b; now++)
        {
            int ok=1;
            for(int k=1; k<i; k++)
                if(count(now^a[k])<d){ok=0;break;}
            if(ok){a[i]=now;break;}
        }
    for(int i=1; i<=n; i++)
        cout << a[i] << " \n"[i%10==0];
    return 0;
}

P1473 [USACO2.3]零的数列 Zero Sum

暴搜，字符串处理会更快些

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(15)
int n,a[N];
string str;
const char ch[10]="$+- ";
bool ck()
{
    str="";
    for(int i=1; i<n; i++)
    {
        str+=char(i+'0');
        if(a[i]!=3)str+=ch[a[i]];
    }
    str+=char(n+'0');
    int i=0,sum=0,now=0,last=1;
    // cout << str << endl;
    while(i<str.size())
    {
        while(isdigit(str[i])&&i<str.size())
            now=now*10+str[i]-'0',++i;
        if(last==1)sum+=now;
        else sum-=now;
        now=0;
        last=str[i++]=='+';
    }
    if(last==1)sum+=now;
        else sum-=now;
    // cout << sum << endl;
    return sum==0;
}
void print()
{
    for(int i=1; i<n; i++)
        printf("%lld%c",i,ch[a[i]]);
    printf("%lld\n",n);
}
void dfs(int u)
{
    if(u==n)
    {
        if(ck())print();
        return;
    }
    a[u]=3;dfs(u+1);
    a[u]=1;dfs(u+1);
    a[u]=2;dfs(u+1);
}
signed main()
{
    scanf("%lld",&n);dfs(1);
    return 0;
}

P1470 [USACO2.3]最长前缀 Longest Prefix

线性dp，~~不过q779太菜了一开始没想到~~（

令 $dp[i]$ 表示位置 $i$ 是否能接上一个新的串

然后就没了，暴力转移就好了

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)
int n,m,ans;
int dp[N];
set<string> s[N];
string t,in;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(cin >> in&&in[0]!='.')
    {
        s[in.size()].insert(in);
        n=max(n,(int)in.size());
    }t="$";
    dp[0]=1;
    while(cin >> in) t+=in;
    m=t.size()-1;
    for(int i=1; i<=m; i++)
        for(int j=min(i,n); j; --j)
        {
            string sub=t.substr(i-j+1,j);
            if(s[sub.size()].count(sub)==1&&dp[i-j])
            {ans=i;dp[i]=1;break;}
        }
    cout << ans << endl;
    return 0;
}