http://www.luogu.org/contest/show?tid=199

?

T1： 集合求和

可以找一下規律，對于一個包含n個元素的集合，每個元素在所有子集中出現的次數均為2^(n-1)，將sum乘這個數即可。

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define ll long long using namespace std; ll x,s,sum; int main() {s=1;while (cin>>x) {sum+=x; s<<=1;};printf("%lld",sum*(s>>1));return 0; }

T2： GCD SUM

我們可以用f[i]表示gcd(x,y)=i的數對共有f[i]個。

從n->1枚舉，首先將f[i]賦值為（n/i）*（n/i），然后去掉f[2*i],f[3*i]....即可。

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define ll long long using namespace std; int n; ll ans,f[100005]; int main() {scanf("%d",&n);for (int d=n;d>=1;d--){f[d]=1ll*(1ll*n/d)*(n/d);for (int i=d+d;i<=n;i+=d) f[d]-=f[i];ans+=f[d]*d;}printf("%lld",ans); }

?

T3： 看球泡妹子

本著騙分的想法寫了個很暴力的dp，f[i][j][k]即前i個比賽選j個目前帥哥值為k，答案即為max{f[m][k][i],c<=i<=sum},特判一下如果最大的k項相加仍<c則無解（否則只有90分）。

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define ll long long using namespace std; int n,m,mx,mn,c,sum,ans; int a[105],b[105],p[105],q[105],s[105]; int f[105][105][2005]; inline int read() {int a=0,f=1; char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}return a*f; } inline bool cmp(int a,int b) {return a>b; } int main() {n=read(); m=read(); mx=read(); c=read(); for (int i=1;i<=n;i++) a[i]=read();for (int i=1;i<=n;i++) b[i]=read();for (int i=1;i<=m;i++) p[i]=read(),q[i]=read(),s[i]=b[p[i]]+b[q[i]];sort(s+1,s+m+1,cmp);for (int i=1;i<=mx;i++) sum+=s[i];if (sum<c) {printf("-1"); return 0;}for (int i=1;i<=m;i++)for (int j=1;j<=mx;j++)for (int k=mn;k<=2000;k++){f[i][j][k]=f[i-1][j][k];if (k-b[p[i]]-b[q[i]]>=0) f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-b[p[i]]-b[q[i]]]+a[p[i]]*a[q[i]]);}for (int i=c;i<=2000;i++) ans=max(ans,f[m][mx][i]);if (!ans) printf("-1"); else printf("%d",ans);return 0; }

?

?

T3第二種方法：

令x[i]=20-(b[p[i]]+b[q[i]]),y[i]=a[p[i]]*a[q[i]].那么若滿足題意就等價于滿足sigma(x[i])<20*k-c;這就成了一個二維費用背包。

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int n,m,K,c,ans; int a[105],b[105],p[105],q[105],x[105],y[105]; int f[105][2005]; inline int read() {int a=0,f=1; char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}return a*f; } int main() {n=read(); m=read(); K=read(); c=read(); c=20*K-c;for (int i=1;i<=n;i++) a[i]=read();for (int i=1;i<=n;i++) b[i]=read();for (int i=1;i<=m;i++) {p[i]=read(); q[i]=read(); x[i]=20-b[p[i]]-b[q[i]]; y[i]=a[p[i]]*a[q[i]];}for (int i=1;i<=m;i++)for (int j=K;j>=1;j--)for (int k=c;k>=x[i];k--) f[j][k]=max(f[j][k],f[j-1][k-x[i]]+y[i]);for (int i=1;i<=c;i++) ans=max(ans,f[K][i]);if (!ans) printf("-1"); else printf("%d",ans);return 0; }

?

?

T4： 電路維修

應該是這次比賽比較難的一道題了，我們可以對每條邊所在格的四個頂點連邊，已相連的權值為0，未相連的權值為1。然后跑最短路就好。

PS：對于判斷無解，則為n+m為奇數，畫個圖即可發現。

PS：我們可以發現有一些點是無論如何都不會走到的，可以忽略這些點，可以省去一半。

PS：spfa80分會TLE，heap+priority_queue可過。

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #define ll long long #define INF 1000000000 #define M 300005 #define pa pair<ll,int> using namespace std; int n,m,cnt; int head[300000],q[300010],dis[300000],next[1200000],list[1200000],key[1200000]; bool v[300000],vis[300000]; priority_queue<pa,vector<pa>,greater<pa> >qq; inline int read() {int a=0,f=1; char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}return a*f; } inline void insert(int x,int y,int z) {next[++cnt]=head[x];head[x]=cnt;list[cnt]=y;key[cnt]=z; } /*inline int spfa() {for (int i=1;i<=n*m;i++) {dis[i]=INF; v[i]=0;}int t=0,w=1,x; dis[1]=0; v[1]=1; q[1]=1;while (t!=w){t=(t+1)%M;x=q[t];for (int i=head[x];i;i=next[i])if (dis[list[i]]>dis[x]+key[i]){dis[list[i]]=dis[x]+key[i];if (!v[list[i]]){v[list[i]]=1;w=(w+1)%M;q[w]=list[i];}}v[x]=0;}return dis[n*m]; }*/ inline int dijkstra() {for(int i=1;i<=m*n;i++)dis[i]=INF;dis[1]=0;memset(vis,0,sizeof(vis));qq.push(make_pair(0,1));while(!qq.empty()){int now=qq.top().second;qq.pop();if(vis[now])continue;vis[now]=1;for(int i=head[now];i;i=next[i])if(dis[now]+key[i]<dis[list[i]]){dis[list[i]]=dis[now]+key[i];qq.push(make_pair(dis[list[i]],list[i]));}}return dis[n*m]; } int main() {int t=read();while (t--){n=read()+1; m=read()+1;if ((n+m)%2==1) {puts("NO SOLUTION"); continue;}for (int i=1;i<n;i++){char c[505];scanf("%s",c+1);if (i%2==1){for (int j=1;j<m;j+=2){if (c[j]!='/') {insert((i-1)*m+j,i*m+j+1,0); insert(i*m+j+1,(i-1)*m+j,0);}else {insert((i-1)*m+j,i*m+j+1,1); insert(i*m+j+1,(i-1)*m+j,1);}}for (int j=2;j<m;j+=2){if (c[j]!='/') {insert(i*m+j,(i-1)*m+j+1,1); insert((i-1)*m+j+1,i*m+j,1);}else {insert(i*m+j,(i-1)*m+j+1,0); insert((i-1)*m+j+1,i*m+j,0);}}}if (i%2==0){for (int j=1;j<m;j+=2){if (c[j]!='/') {insert(i*m+j,(i-1)*m+j+1,1); insert((i-1)*m+j+1,i*m+j,1);}else {insert(i*m+j,(i-1)*m+j+1,0); insert((i-1)*m+j+1,i*m+j,0);}}for (int j=2;j<m;j+=2){if (c[j]!='/') {insert((i-1)*m+j,i*m+j+1,0); insert(i*m+j+1,(i-1)*m+j,0);}else {insert((i-1)*m+j,i*m+j+1,1); insert(i*m+j+1,(i-1)*m+j,1);}}}}printf("%d\n",dijkstra());for (int i=1;i<=n*m;i++) head[i]=0; cnt=0;}return 0; }

?

?

第一次AK……紀念一下。

轉載于:https://www.cnblogs.com/ws-fqk/p/4735123.html

總結

以上是生活随笔為你收集整理的CONTEST199 [有奖]洛谷8月月赛题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。