【19HDU多校】Rikka with Coin,贪心

传送门

题意是说有面值10 20 50 100的钱,有n个价格给定的菜,要求用最少的硬币数量,使得所有n个菜品的价格都能被凑出来。

贪心:直观想法是先用大的面值,依次用小的面值。

这样的话可以发现10, 20, 20, 50四个面值能凑出所有100以内的价格。

但是有个例外:90 110 这样的数据,如果按照上面的贪法是100 50 20 20 10五个硬币,实际上只需要50 20 20 20四个硬币就可以拼出来。

所以进一步发现用10 20 20 20 50五个硬币可以包含所有最优方案。两个10肯定能用一个20代替,四个20肯定能用一个50 20 10代替。

所以做一个10 20 20 20 50的子集生成。然后暴力判断dish[i] % 100 + 100dish[i] % 100在某个组合的子集生成里有没有。(有先后顺序,第一个如果有了第二个就不用判断。因为既然零钱数量是固定的,那么100圆的越少约好)如果有,100圆的数量就分别是(dish[i] - (dish[i] % 100 + 100)/ 100) ,和dish[i] / 100

对于100圆判断是个重要细节。
比如1000 90 110这样的数据,1000其中的100圆可以用零钱拼出来,所以100圆个数只有9个。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5] = {10, 20, 20, 20, 
Read the rest

【2019多校】HDU6627 equation

传送门

题意是给出若干个一次函数的绝对值,问方程的所有解

把函数按照零点排序,在零点左边的函数都取负,右边都取正。

然后把若干个一次函数看成一个一次函数,用公式直接求解

有个坑点是ax+b=c判断无穷解的时候,除了a等于0以外。还需要b=c,否则是无解,不是无穷解。

#include<bits/stdc++.h>
using namespace std;
typedef __int128 lll;
typedef long long ll;
const int maxn = 1e6 + 233;
typedef pair<ll,ll> pii;
pii v[maxn];
bool cmp(const pii &x, const pii &y)
{
    if( y.first * x.first > 0) return  -x.second * y.first <  -y.second * x.first;
    else return  -x.second * y.first >  -y.second * x.first;
}
bool cmp2(const pii &x, const pii &y)
{
    if( x.second * y.second > 0) return  x.first * y.second <  y.first 
Read the rest

【2019HDU多校】扩展kmp模板题

传送门

扩展KMP模板题

要你求对于每个后缀,与前缀匹配的最大长度

是我太菜了,居然不知道有这个算法。。。。。被签到题自闭十万年

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 233;
typedef long long ll;
bool vis[maxn];
char a[maxn], b[maxn];
int nxt[maxn], f[maxn];
int main()
{
    int T; cin >> T;
    while(T--)
    {
        scanf("%s" , a);
        int n = strlen(a);
        memset(nxt, 0, sizeof nxt);
        nxt[0] = n;
        int j = 0;
        while(j + 1 < n && a[j] == a[j + 1]) j++;
        nxt[1] = j;
        int p0 = 1;
        for(int i = 2; i < 
Read the rest

【2019HDU多校】HDU6579 线性基

传送门

题意是说会依次给m次操作,要么在序列后面加一个数,要么问你区间[L, R]里的最大异或和。

做法很有技巧。维护前缀的线性基。f[x][i]代表前x个数第i位的代表的基是哪个数。

但是不是一般的方法直接维护,而是只留下最靠后加入的。所以还需要一个pos[x][i]代表f[x][i]是第几个数。

这样在查询f[r][i]的时候如果第i位的pos是小于l的(pos[r][i] < l),这一位就不合法舍去。

因为在插入的时候是在此位存在的情况下维护尽量靠后的。所以答案一定是最大的。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 233;
int f[maxn][33], pos[maxn][33];
inline int Read() 
{
    int x=0,f=1; char ch=getchar(); 
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f; ch=getchar();}
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
char s[30];
inline void writeln(int x)
{
    if (x<0) putchar('-'),x=-x; 
    if (!x) putchar('0'); else 
    {
        int len=0;  
        while (x) s[++len]=x%10+'0',x/=10;
          while (len) putchar(s[len--]);
    } 
    putchar('\n');
}
void add(int x, int v)
{
    for(int i = 30; i 
Read the rest