我这个代码能力下降到\rm{-INF}了
并查集板子打了15分钟 还有谁？？
气死了
算了赶紧写完赶紧睡觉
A. Mahmoud and Ehab and the even-odd game（真长）
就这题！！！卡了我五分钟！！我觉得它长的像SG，是它的错还是我的？！
一定注意a \leq n！！
然后你就会发现这游戏最多就一轮
|
1 2 3 4 5 6 7 8 9 10 |
#include<cstdio> #include<iostream> #include<cstring> using namespace std; int main() { int n; scanf("%d",&n); if (n%2) cout<<"Ehab"<<endl; else cout<<"Mahmoud"<<endl; } |
B. Mahmoud and Ehab and the message（这个更长？）
然后并查集板子+map……能这个点打Cf的都能看出来也不说了……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<queue> #include<vector> #include<cstdlib> #include<iterator> #include<algorithm> #include<map> #define ll long long using namespace std; int fa[100010]={0},hea[100010]={0}; ll cost[100010]={0},minc[100010]={0}; char words[100010][30]={0},mes[30]={0}; int n,kx,m,cache1,siz; ll ans=0; map <string,int> mapx; inline void readx(int& x) { x=0; int k=1; register char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } inline int findx(int e) { if (fa[e]!=e) fa[e]=findx(fa[e]); return fa[e]; } inline void mergex(int a,int b) { fa[findx(b)]=findx(a); } int main() { readx(n); readx(kx); readx(m); for (int i=1;i<=n;i++) fa[i]=i; for (int i=1;i<=n;i++) { scanf("%s",words[i]); mapx[words[i]]=i; } for (int i=1;i<=n;i++) scanf("%lld",&cost[i]); for (int i=1;i<=kx;i++) { readx(siz); readx(hea[i]); minc[hea[i]]=cost[hea[i]]; for (int j=2;j<=siz;j++) { readx(cache1); mergex(hea[i],cache1); minc[hea[i]]=min(minc[hea[i]],cost[cache1]); } } for (int i=1;i<=m;i++) { scanf("%s",mes); ans+=minc[findx(mapx[mes])]; } cout<<ans<<endl; return 0; } |
C. Mahmoud and Ehab and the wrong algorithm（哇，还是这么长）
送分(ming)构造题
两问分别长这样
注意第一问只有n \geq 5才有解……原因是层数和两个点的解的限制（也就是说第二层最少3个点然后第三层必须有两个点及以上((一个点的话那个算法也是正确的))）
D. Mahmoud and Ehab and another array construction task（最长！）
这题，扫一下然后质因数分解
如果分解有重那么立即断开，前面的原样输出，后面的贪心地选一个质数输出
注意特判
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<queue> #include<vector> #include<cstdlib> #include<iterator> #include<algorithm> #define ll long long using namespace std; int n,seq[2000010]={0},vis[2000010]={0}; int tvis[10010]={0},cpos,pnum[2000010]={0}; bool nnum[2000010]={0}; inline void readx(int& x) { x=0; int k=1; register char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } inline void EulerShake(ll upat) { int ctr1=0; nnum[0]=nnum[1]=true; for (ll i=2;i<=upat;i++) { if (!nnum[i]) pnum[++ctr1]=i; for (int j=1;j<=ctr1 && pnum[j]*i<=upat;j++) { nnum[i*pnum[j]]=true; if (!(i%pnum[j])) break; } } } inline bool divi(int nq) { int upat=sqrt(nq)+1,n1=nq; cpos=0; for (int i=2;i<=upat;i++) { if (n1%i==0) { tvis[++cpos]=i; n1=n1/i; upat=sqrt(n1)+1; } while (n1%i==0) { n1=n1/i; upat=sqrt(n1)+1; } } if (n1!=0 && n1!=1) tvis[++cpos]=n1; return 1; } inline bool solve(int now) { divi(now); for (int i=1;i<=cpos;i++) if (vis[tvis[i]]) return false; for (int i=1;i<=cpos;i++) vis[tvis[i]]=1; return 1; } int main() { readx(n); EulerShake(2000000); for (int i=1;i<=n;i++) readx(seq[i]); for (int i=1;i<=n;i++) { if (!solve(seq[i])) { for (int j=1;j<i;j++) printf("%d ",seq[j]); for (int j=seq[i]+1;;j++) if (solve(j)) { printf("%d ",j); break; } int pos=1; for (int j=i+1;j<=n;j++) { while (vis[pnum[pos]]) pos++; printf("%d ",pnum[pos]); pos++; } printf("\n"); return 0; } } for (int i=1;i<=n;i++) printf("%d ",seq[i]); printf("\n"); return 0; }<span id="mce_marker" data-mce-type="bookmark" data-mce-fragment="1"></span> |
E. Mahmoud and Ehab and the xor-MST（哈！变短了吧！）
我们考虑……有什么好考虑的。。。
那就……从高位来考虑？
当前考虑的，要求mst的点集的所有点权，在目前位上, 必然是n_1 \text{ — } n_x这一部分是0，然后n_{x+1} \text{ — } n_{last}是1，那么点 x+1 \text{ — } last之间独立连边，1 \text{ — } x之间独立连边，这么做，可以保证对答案贡献都是0，是最优的。
·
但是如果当前确实有一个满足上述条件的x存在的话，
（其实也就是现在考虑的点集的最大点权的点，点权模掉2^{w-1}大于等于2^w，其中w是当前考虑的位数）
（也就是这一位上有1的出现，所以点被划成了这一位是0 \; , \; 1两个子点集）
那么还要把左右两个点集联通。先加上这样的代价 ：2^w。
·
我们其实并不关心这两个点集是怎么内部联通的，因为这个可以递归求解。把两个点集的点权模掉2^w之后就成为子问题了，对吧？
但是0集那个子问题是可以预处理的，要不然会T。
f[i]表示从0到2^i-1的贡献和。怎么转移？这个其实就是……你把它按照上面我说的拆一下点集就好了。然后方程在这儿：f[i]=2*f[i-1]+(1LL<<w-1)这个不难理解吧……
我希望我这题说明白了.
(我怕我long long的位运算出锅于是打了快速幂……）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<queue> #include<vector> #include<cstdlib> #include<iterator> #include<algorithm> #define ll long long using namespace std; ll f[100]={0}; ll n,ans=0; inline ll fastpow(ll a,int p) { ll ret=1; for (;p;p>>=1,a*=a) if (p&1) ret*=a; return ret; } inline void solve1(ll now,int w) { if (w<0) return; ll mo=fastpow(2,w+1),lowx=fastpow(2,w); if (now%mo>=lowx)//1 { ans+=lowx+f[w]; solve1(now%lowx,w-1);//1 part } //all 0 else solve1(now,w-1); } int main() { scanf("%lld",&n); n--; for (int i=1;i<=40;i++) f[i]=2*f[i-1]+fastpow(2,i-1); for (int w=40;w>=0;w--) { ll upat=fastpow(2,w); if (n>=upat) { solve1(n,w); break; } } cout<<ans<<endl; return 0; } |
F. Mahmoud and Ehab and yet another xor task
留坑