Lead of Wisdom
http://acm.hdu.edu.cn/showproblem.php?pid=6772
暴力搜索,但是要稍微优化一下,特别是num[x]==0的情况要在dfs前预处理一下;
#include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long LL; struct Node{ LL a,b,c,d; }; int n,k; LL ans; LL n1,n2,n3,n4; vector<Node> it[100]; vector<int> v; void dfs(int x){ if(x>=v.size()){ ans = max(ans,n1*n2*n3*n4); return ; } int t = v[x]; for(int i=0;i<it[t].size();i++){ n1+=it[t][i].a,n2+=it[t][i].b,n3+=it[t][i].c,n4+=it[t][i].d; dfs(x+1); n1-=it[t][i].a,n2-=it[t][i].b,n3-=it[t][i].c,n4-=it[t][i].d; } } int main(){ int T; scanf("%d",&T); LL t,a,b,c,d; while(T--){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%lld%lld%lld%lld%lld",&t,&a,&b,&c,&d); it[t].push_back({a,b,c,d}); v.push_back(t); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); ans=0,n1=100,n2=100,n3=100,n4=100; dfs(0); cout<<ans<<"\n"; for(int i=0;i<=k;i++) it[i].clear(); v.clear(); } return 0; }
The Oculus
http://acm.hdu.edu.cn/showproblem.php?pid=6768
这个题是一道数学思维题,根据题意A∗B=C+f[i]A∗B=C+f[i]; 所以 f[i]=A∗B−Cf[i]=A∗B−C;由于数比较大,所以直接两边同时取模,但是要保证对于任意 i!=j,要有 f【i】(modp)!=f【j】(modp)i!=j,要有f【i】(modp)!=f【j】(modp)
#include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long LL; const int N = 2e6+10; const int mod = 887654321; LL f[N]; int n,k,t; int main(){ f[0]=1,f[1]=1; for(int i=2;i<N;i++) f[i] = (f[i-1]+f[i-2])%mod; int T; scanf("%d",&T); while(T--){ scanf("%d",&n); LL a=0,b=0,c=0; for(int i=1;i<=n;i++){ scanf("%d",&t); a=(a+f[i]*t)%mod; } scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&t); b=(b+f[i]*t)%mod; } scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&t); c=(c+f[i]*t)%mod; } LL ans=(a*b%mod-c+mod)%mod; for(int i=1;i<=n;i++) if(f[i]==ans){ printf("%d\n",i); continue; } } return 0; }