C – Dice Sum

题目描述：

问存在多少种序列A,满足如下的条件：

• 长度为n
• A[i] <= m
• $\sum_{i=1}^{n}{A[i]}<=K$

思路：

我们可以把他看成一个二维费用的背包问题

每个物品的体积是1,重量是i,背包的总体积是n,承载重量是K

问的是方案数

dp[j][k]表示当前体积是j，用了k的重量的方案数

状态转移方程： $dp[j][k] += dp[j - 1][k - i]$

如果我们for循环先枚举物品i，再枚举两种费用，那就是错误的，因为相当于数组的大小顺序已经确定了，但是这个题1 2和2 1两个数组是不同的，所以我们应该先枚举两种费用，再枚举物品i

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, kk, x;
ll dp[55][3005];

void work(){
    cin >> n >> m >> kk;
    dp[0][0] = 1;
    for(int j = 1; j <= n; ++j){
        for(int k = 1; k <= kk; ++k){
            for(int i = 1; i <= m; ++i){
                if(k >= i)(dp[j][k] += dp[j - 1][k - i]) %= mod9;
            }
        }
    }
    ll ans = 0;
    for(int i = 1; i <= kk; ++i){
        (ans += dp[n][i]) %= mod9;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

D - Range Count Query

题目描述：

给一个数组A[i]，q次询问，每次询问都问[l, r]中等于x的数的数量

思路：

我们可以给每种数都开一个数组，把等于他的所有的id都顺次放进去，对于每个询问，我们去对应的数组二分即可

（开始写了个莫队，结果不出意料的T掉了

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x, l, r;
vector<int>tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> x;tr[x].push_back(i);
    }
    cin >> m;
    for(int i = 1; i <= m; ++i){
        cin >> l >> r >> x;
        if(tr[x].size() == 0)cout << 0 << endl;
        else{
            ll lp = lower_bound(tr[x].begin(), tr[x].end(), l) - tr[x].begin();
            ll rp = upper_bound(tr[x].begin(), tr[x].end(), r) - tr[x].begin();
            if(lp == tr[x].size()){
                cout << 0 << endl;
                continue;
            }
            cout << rp - lp<< endl;
        }
    }
}


int main(){
    io;
    work();
    return 0;
}

E - K-colinear Line

题目描述：

n个点，问存在多少条不同的直线，使的直线上的点的数量大于等于x

思路：

两点确定一条直线，所以我们直接枚举每两个点，得到一个直线，再枚举剩下的所有的点，看有多少个点在线上，如果数量大于等于k，就更新答案，个人感觉这个题主要考的是直线的判重，这里因为数据量很小，我们直接用vector存下来每次符合条件的点的所有下标，然后排个序，扔到set里面去重，最后只需要输出set的大小即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
#define int long long

typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x, y;
vector<pii>v;
set<vector<int>>se;

bool judge(int i, int j, int k){
    int a = v[k].second - v[i].second;
    int b = v[k].first - v[i].first;
    int c = v[j].second - v[i].second;
    int d = v[j].first - v[i].first;
    if(a * d == b * c)return true;
    return false;
}

void work(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> x >> y;
        v.push_back(m_p(x, y));
    }
    if(k == 1){
        cout << "Infinity\n";
        return;
    }
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            int mx = min(v[i].first, v[j].first);
            int my = min(v[i].second, v[j].second);
            int num = 2;
            vector<int>vv;
            vv.push_back(i);vv.push_back(j);
            for(int k = 0; k < n; ++k){
                if(k == i || k == j)continue;
                if(judge(vv[(int)vv.size() - 2], vv[(int)vv.size() - 1], k)){
                    ++num;
                    vv.push_back(k);
                    mx = min(mx, v[k].first);
                    my = min(my, v[k].second);
                }
            }
            if(num >= k){                sort(vv.begin(), vv.end());
                se.insert(vv);
            }
        }
    }
    cout << se.size() << endl;
}


signed main(){
    io;
    work();
    return 0;
}