wap 5.23 网测几道题目

1. n个犯人，m个省份，如果相邻的2个犯人来自同一省份，则是不安全的，求不安全的个数。

正难则反，用全部的个数减去非法的个数，就是最后的答案。 m^n - m * (m - 1) ^ (n - 1). 这里的m,n很大，所以就是快速幂乘法。

 #include<bits/stdc++.h>

 #define pb push_back

 typedef long long ll;

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 1e3 + ;

 const int mod = ;

 ll n, m;

 ll pow(ll x, ll y) {

     if(y == ) return ;

     ll r = ;

     ll b = x;

     while(y) {

         if(y & ) {

             r = r * b % mod;

         }

         y >>= ;

         b = b * b % mod;

     }

     return r;

 }

 void solve() {

     cin >> m >> n;

     //cout << m<< " " << n <<endl;

     //cout << pow(m, n) << endl;

     //cout << pow(m, n - 1) << endl;

     ll res = ((pow(m, n) - pow(m - , n - ) * m) % mod + mod)%mod;

     cout << res << endl;

 }

 int main() {

     freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     ios::sync_with_stdio();

     cin.tie(); cout.tie();

     solve();

     return ;

 }

2. 从n个数，选取一些数，使得能被m整除。

这种题，就是一般的套路，搞一下余数，然后就是0,1背包。注意一维数组优化，滚动数组，取余。

 #include<bits/stdc++.h>

 #define pb push_back

 typedef long long ll;

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 1e6 + ;

 int n, m;

 int a[maxn];

 void yes() {

     cout << "Yes" << endl;

 }

 void no() {

     cout << "No" << endl;

 }

 int dp[][maxn];

 void solve() {

     scanf("%d%d", &n, &m);

     int x, y;

     for (int i = ; i < n; i++) {

         scanf("%d", &x);

         x = x % m;

         a[x]++;

     }

     if(a[] > ) {

         yes(); return;

     }

     dp[][] = ;

     vector<int> av;

     for (int i = ; i <= m - ; i++) {

         for (int j = ; j < a[i]; j++)

             av.push_back(i);

             //cout << i << endl;

     }

     //cout << "asd" << endl;

     int cur = , nxt = ;

     for (int tx : av) {

         for (int i = m - ; i >= ; i--) {

             if(dp[cur][i] > ) {

                 dp[nxt][i] = ;

                 int t = (i + tx) % m;

                 if(t == ) t = m;

                 dp[nxt][t] = ;

                 //cout << t << endl;

             }

         }

         swap(cur, nxt);

         for (int i = ; i < m; i++)

             dp[nxt][i] = ;

         //cout << tx << endl;

     }

     if(dp[cur][m]) yes();

     else no();

 }

 int main() {

     freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     solve();

     return ;

 }

3. 有一些操作，插入和查询，插入是往末尾进行插入，查找的是末尾长度为l的里面的最大值。

由于每次动态更新，区间不停的变换，我只想到线段树的做法，就写了线段树的。logn单点更新， logn区间查询。

 #include<bits/stdc++.h>

 #define pb push_back

 typedef long long ll;

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 2e5 + ;

 ll f[maxn * ];

 int n;

 int x, y;

 ll v;

 void bt(int o, int left, int right) {

 }

 void add(int o, int left, int right) {

     if(left > right) return;

     if(left == right && left == x) {

         f[o] = v;

     } else {

         int mid = (left + right) / ;

         if(x <= mid) add(o * , left, mid);

         else add(o *  + , mid + , right);

         f[o] = max(f[o * ], f[o *  + ]);

     }

 }

 ll ask(int o, int left, int right) {

     if(right < x || y < left) return ;

     if(x <= left && right <= y) return f[o];

     int mid = (left + right) / ;

     ll ml, mr;ml = mr = ;

     if(x <= mid) ml = ask(o * , left, mid);

     if(y >= mid + ) mr = ask(o *  + , mid + , right);

     return max(ml, mr);

 }

 int m;

 ll mod;

 char ch[];

 void solve() {

     scanf("%d%lld", &m, &mod);

     int p = ;

     ll lst = , t;

     for (int i = ; i < m; i++) {

         //cout << i << endl;

         scanf("%s%lld", ch, &t);

         if(ch[] == 'I') {

             t = (t + lst) % mod;

             x = ++p; v = t;

             add(, , m);

         } else {

             if(t == ) {

                 printf("0\n");

                 continue;

             }

             x = p - t + ;

             y = p;

             lst = ask(, , m);

             printf("%lld\n", lst);

         }

     }

 }

 int main() {

     freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     solve();

     return ;

 }

4. 逆序对，现在有1-n，一共n个数，求逆序对的个数为m的排列的个数。1 <= n,m <= 1000.

枚举，数个数，贪心的方式是不行的，那就是dp了。

枚举最大的一个数，看如何进行转移。dp[i][j] 代表长度为i, 逆序对的个数为j的个数。考虑从dp[i-1]转移过来，增加的逆序对的个数，就很容易写出来转移方程。

写出来之后，发现时间复杂度是n^3的，不满足要求，然后用前缀和维护一下，使得0（1）的求取区间的和。使得复杂度降为n^2.

 #include<bits/stdc++.h>

 #define pb push_back

 typedef long long ll;

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 1e3 + ;

 const int mod = ;

 int n, k;

 int dp[maxn][maxn];

 int s[maxn][maxn];

 void solve() {

     cin >> n >> k;

     for (int i = ; i <= n; i++) {

         dp[i][] = ;

         s[i][] = ;

         for (int j = ; j <= k; j++) {

             dp[i][j] = s[i - ][j];

             if(j - i >= )

                 dp[i][j] = (dp[i][j] - s[i - ][j - i] + mod) % mod;

             s[i][j] = (s[i][j - ] + dp[i][j]) % mod;

             //cout << i << " " << j << " " << dp[i][j] << endl;

         }

     }

     cout << dp[n][k] << endl;

 }

 int main() {

     freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     ios::sync_with_stdio();

     cin.tie(); cout.tie();

     solve();

     return ;

 }

巴特西

wap 5.23 网测几道题目

最新文章

热门文章