gift
题目描述
战争结束，A国和B国的元首决定两国友好相处，于是城市之间就有互相送礼的情况。
参与这次相互协助计划中有n个A国的城市和m个B国的城市。作为A国的重臣，小Q了解到每一个A国的城市送出了ai份礼物，B国的城市收到了bi份礼物，城市之间不会重复送礼，并且A国和B国自己的城市之间不会送礼。
有一句老话“眼见为实，耳听为虚”，现在小Q想知道是否存在一种送礼的方案使得每一个城市都满足要求。
输入
第一行一个整数T，表示小Q询问的次数。
接下来有T组询问，每一组询问第一行为两个正整数n,m，表示A国的城市数和B国的城市数。
第二行给出n个整数ai，表示A国第i个城市送出的礼物数。
第三行给出n个整数bi，表示B国第i个城市收到的礼物数。
输出
共T行，每行输出Yes或No表示是否存在一种合法方案。
样例输入 Copy
3 1 2 2 1 1 2 2 1 1 1 2 5 2 2 1 1 1 0 0 5
样例输出 Copy
Yes No No
提示
样例解释
第一组数据中A国只有一个城市，送给B国两个城市共两个礼物。
第二组数据中A国总共送出2个礼物，但是B国共收到3个，显然矛盾。
第三组数据中A国的第一个城市给B国的第二个城市送了超过一个礼物，矛盾。
对于100%的数据，满足T≤10,1≤n,m≤1000,0≤ai≤m,0≤bi≤n。
根据通过率来看，此题有坑，首先我个人来说没有看见B国的城市只能是接受A国一个城市的礼物，换句话说就是B只能接受一个礼物，不能接受两个礼物本蒟蒻在这里卡了9%
然后暴力了一波之后发现，通过不了
根据dl的神仙思路，统计A中的最大值、最小值、和、非零个数
统计B中非零的个数、等于n的个数、和
如果两方的数量和不相同，那么必定就是No
如果B中的元素大小如果超过A中的非零的个数，那么就意味着B中一定是会接手两个A的礼物，因此，这种情况必定是No
如果A中最大大于B里面非零的个数，也是No
如果B里面等于n的个数大于A中的最小值，这种情况也是No
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const ll INF = 0x3f3f3f3f; const int maxn = 3e5 + 7; const int mod = 998244353; #define pi 3.14159265358979323846 ll gcd(ll a,ll b) { ll t; while(b!=0) { t=a%b; a=b; b=t; } return a; } ll qPow(ll x, ll k) { ll res = 1; while(k) { if(k&1) res=(res*x); k>>=1; x=(x*x); } return res; } ll maxx=-1; ll minn=inf; ll num[maxn]; ll num2[maxn]; ll res,ans; map<string,ll> mp; priority_queue <int ,vector<int> ,greater<int> > xiaogen; deque<int> q; ll a[maxn],b[maxn]; ll wrkc[502][502]; int main() { ///gift int T=read; while(T--){ int n=read,m=read; ll sum1=0; ll sum2=0; int flag=1; maxx=0,minn=INF; int cnt1=0,cnt2=0,cnt3=0; for(int i=1;i<=n;i++){ a[i]=read; sum1+=a[i]; if(a[i]>maxx) maxx=a[i]; if(a[i]){ cnt1++; if(minn>a[i]) minn=a[i]; } } for(int i=1;i<=m;i++){ b[i]=read; if(b[i]) cnt2++; if(b[i]>cnt1) flag=0; sum2+=b[i]; if(b[i]==n) cnt3++; } if(sum1!=sum2) flag=0; if(cnt3>minn) flag=0; if(maxx>cnt2) flag=0; if(flag) printf("Yes\n"); else printf("No\n"); } return 0; } /** 3 1 2 2 1 1 2 2 1 1 1 2 5 2 2 1 1 1 0 0 5 **/ /************************************************************** Problem: 15362 Language: C++ Result: 正确 Time:2 ms Memory:13380 kb ****************************************************************/
魔法阵
题目描述
很久以前，遥远的盘古大陆有三个村：苹果村、梨子村和香蕉村
有一天，伟大的魔法师kiwi发明了一种魔法阵，如下图
苹果村有A个村民，梨子村有B个村民，香蕉村有C个村民
苹果村每个村民有a[i]个苹果，梨子村每个村民有b[i]个梨子，香蕉村每个村民有c[i]个香蕉
Kiwi会选择三个村的村民各一个，每个村民会从自己拥有的水果中任意选择应有的数量个（苹果3个，梨子2个，香蕉1个）放入魔法阵中
Kiwi认为每个水果都是不同的，两个魔法阵不同当且仅当放入的水果至少有一个不同
也就是说，与每个水果在魔法阵中的位置无关
Kiwi想知道魔法阵一共可能有多少种，对998244353取模
输入
第一行3个数A,B,C
第二行A个数表示a[i]
第三行B个数表示b[i]
第四行C个数表示c[i]
输出
一行表示魔法阵一共可能有多少种，对998244353取模
样例输入
1 2 1 3 2 3 1
样例输出
4
提示
Kiwi只能选择仅有的苹果村村民和香蕉村村民，而他们也只能拿出全部的水果
如果他选择了第1个梨子村村民，那么他也只能拿出全部梨子
如果他选择了第2个梨子村村民，设他的梨子分别叫1,2,3，那么他可以拿{1,2}{1,3}{2,3}
a[i]>=3,b[i]>=2,c[i]>=1
对于前30%的数据：A,B,C,a[i],b[i],c[i]<=6
对于前60%的数据：A,B,C<=100，a[i],b[i],c[i]<=20
对于前80%的数据：A,B,C<=2000
对于100%的数据：A,B,C<=100000，a[i],b[i],c[i]<=500
这就是组合数比较裸的题，根据高中的分类加法分步乘法来说，先分别统计A B C中各有多少种方法，然后再将这三种方法相乘就是最终结果
需要注意的是数据可能很大请不要吝啬趋于，否则容易40%
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const ll INF = 0x3f3f3f3f; const int maxn = 3e5 + 7; const int mod = 998244353; #define pi 3.14159265358979323846 ll gcd(ll a,ll b) { ll t; while(b!=0) { t=a%b; a=b; b=t; } return a; } ll qPow(ll x, ll k) { ll res = 1; while(k) { if(k&1) res=(res*x); k>>=1; x=(x*x); } return res; } ll maxx=-1; ll minn=inf; ll num[maxn]; ///ll a[maxn]; ll num2[maxn]; ll res,ans; map<string,ll> mp; priority_queue <int ,vector<int> ,greater<int> > xiaogen; deque<int> q; ll a[maxn],b[maxn],c[maxn]; ll wrkc[502][502]; int main() { for(int i=0;i<=501;i++){ wrkc[i][i]=1; wrkc[i][0]=1; } for(int i=1;i<=501;i++){ for(int j=1;j<i;j++){ wrkc[i][j]=(wrkc[i-1][j]%mod+wrkc[i-1][j-1]%mod)%mod; } } ///cout<<wrkc[6][2]<<endl; int aa=read,bb=read,cc=read; for(int i=1;i<=aa;i++) a[i]=read; for(int i=1;i<=bb;i++) b[i]=read; for(int i=1;i<=cc;i++) c[i]=read; ans=1; ll temp1=0,temp2=0,temp3=0; for(int i=1;i<=aa;i++){ temp1+=wrkc[a[i]][3]%mod; temp1%=mod; } for(int i=1;i<=bb;i++){ temp2+=wrkc[b[i]][2]%mod; temp2%=mod; } for(int i=1;i<=cc;i++){ temp3+=c[i]%mod; temp3%=mod; } ans=(temp1%mod)*(temp2%mod)%mod*temp3%mod; cout<<ans%mod<<endl; return 0; } /** 1 2 1 3 2 3 1 **/ /************************************************************** Problem: 15364 Language: C++ Result: 正确 Time:27 ms Memory:15724 kb ****************************************************************/
48位大咖的思考法则、工作方式、逻辑体系
