2018年11月1日提高组

题目

(洛谷 2158仪仗队)

分析

(∑i&＃61;2nphi(i)×2)&＃43;1(\sum_{i&＃61;2}^nphi(i)\times 2)&＃43;1(i&＃61;2∑n​phi(i)×2)&＃43;1&＃xff0c;用线性筛解决

代码

#include
#define rr register
using namespace std;
int phi[100001]&＃61;{0,1},v[100001],prime[10001],n,cnt; long long ans&＃61;1;
signed main(){scanf("%d",&n);for (rr int i&＃61;2;i<n;&＃43;&＃43;i){if (!v[i]) v[i]&＃61;prime[&＃43;&＃43;cnt]&＃61;i,phi[i]&＃61;i-1;for (rr int j&＃61;1;prime[j]*i<&＃61;n;&＃43;&＃43;j){v[i*prime[j]]&＃61;prime[j];phi[i*prime[j]]&＃61;phi[i]*(prime[j]-(i%prime[j]>0));if (i%prime[j]&＃61;&＃61;0) break;}}for (rr int i&＃61;1;i<n;&＃43;&＃43;i) ans&＃43;&＃61;phi[i]<<1;if (n&＃61;&＃61;1) ans&＃61;0;printf("%lld",ans);return 0;
}


题目

(poj 1456 supermarket)

分析

可以用小根堆维护时间&＃xff0c;尽量留大的

代码

#include
#include
#include
#define rr register
using namespace std;
struct rec{int tim,hap;}a[200001];
int n,tot; priority_queue<int>q; long long ans;
inline signed iut(){rr int ans&＃61;0,f&＃61;1; rr char c&＃61;getchar();while ((c<48||c>57)&&c!&＃61;&＃39;-&＃39;) c&＃61;getchar();if (c&＃61;&＃61;&＃39;-&＃39;) f&＃61;-f,c&＃61;getchar();while (c>47&&c<58) ans&＃61;(ans<<3)&＃43;(ans<<1)&＃43;c-48,c&＃61;getchar();return ans*f;
}
signed cmp(rec x,rec y){if (x.tim!&＃61;y.tim) return x.tim<y.tim;else return x.hap>y.hap;
}
signed main(){n&＃61;iut();for (rr int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){rr int x&＃61;iut(),y&＃61;iut();if (y<&＃61;0) continue;a[&＃43;&＃43;tot]&＃61;(rec){x,y}; }sort(a&＃43;1,a&＃43;1&＃43;tot,cmp);for (rr int i&＃61;1;i<&＃61;tot;&＃43;&＃43;i)if (a[i].tim>q.size()) q.push(-a[i].hap);else if (q.size()&&a[i].hap>-q.top()) q.pop(),q.push(-a[i].hap);//可能什么都没有while (q.size()) ans-&＃61;q.top(),q.pop();return !printf("%lld",ans);
}


题目

一个有向图&＃xff0c;找出最大的点集&＃xff0c;使连接该点(必须是被指向)的边的点(指向该点)不属于该点集

分析

贪心&＃xff0c;可以发现找到奇环的时候&＃xff0c;那么个数就是奇环的点数
当链的时候就用拓扑从入度为0的点模拟

代码

#include
#include
#define rr register
using namespace std;
const int N&＃61;1000001; queue<int>q;
int n,ans,deg[N],a[N],v[N];
inline signed iut(){rr int ans&＃61;0; rr char c&＃61;getchar();while (c<48||c>57) c&＃61;getchar();while (c>47&&c<58) ans&＃61;(ans<<3)&＃43;(ans<<1)&＃43;c-48,c&＃61;getchar();return ans;
}
signed main(){n&＃61;iut();for (rr int i&＃61;0;i<&＃61;n;&＃43;&＃43;i) deg[i]&＃61;v[i]&＃61;0;for (rr int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) &＃43;&＃43;deg[a[i]&＃61;iut()];for (rr int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) if (!deg[i]) q.push(i);//拓扑排序while (q.size()){rr int x&＃61;q.front();if (!v[a[x]]&&!v[x]){//当这条链可行ans&＃43;&＃61;v[a[x]]&＃61;1;if (!(--deg[a[a[x]]])) q.push(a[a[x]]);//继续找链}v[x]&＃61;1; q.pop();}for (rr int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)if (!v[i]){rr int cnt&＃61;1;int t&＃61;i;while (a[t]!&＃61;i) cnt&＃43;&＃61;v[t]&＃61;1,t&＃61;a[t];//判环v[t]&＃61;1; ans&＃43;&＃61;cnt>>1;//环内也就是环的点数/2}printf("%d",ans);return 0;
}


我又菜了