A.Little C Loves 3 I
题意&＃xff1a;给定一个整数N&＃xff0c;问是否存在整数a b c使得a&＃43;b&＃43;c&＃61;N且a b c均不为3的倍数
题解&＃xff1a;考虑到mod3的余数只有0 1 2&＃xff0c;所以直接取1,1,N-2 或 1,2,N-3 或 2,2,N-4
代码&＃xff1a;
#include
#include
#include
#include
#include
using namespace std;int N;int main(){cin >> N;if((N-2)%3) cout <<1 <<&＃39; &＃39; <<1 <<&＃39; &＃39; <
}
B.Cover Points
题意&＃xff1a;给定平面上N个第一象限内的整数点&＃xff0c;求一条斜率为-1的直线&＃xff0c;使得所有点都在这条直线的下方
题解&＃xff1a;找截距最大的就行
代码&＃xff1a;
#include
#include
#include
#include
#include
using namespace std;int Ans,N;int main(){cin >> N;for(int i&＃61;1,x,y;i<&＃61;N;i&＃43;&＃43;){cin >> x >> y;Ans&＃61;max(Ans,x&＃43;y);}cout <
}
C.Enlarge GCD
题意&＃xff1a;给定N个数&＃xff0c;求删除最少的数&＃xff0c;使得剩余数的最大公约数严格大于原来的最大公约数
题解&＃xff1a;先把所有的数除以最大公约数&＃xff0c;则问题转化为求最大公因数不为1的最多的个数。枚举因子&＃xff0c;统计答案。
#include
#include
#include
#include
#include
using namespace std;const int MAXN&＃61;300000&＃43;2;
const int MAXM&＃61;15000000&＃43;2;
int a[MAXN],N,g,c[MAXM],Ans,U;
bool Flag[MAXM];int gcd(int a,int b){if(a<b) swap(a,b);return b?gcd(b,a%b):a;
}int main(){cin >> N;for(int i&＃61;1;i<&＃61;N;i&＃43;&＃43;){cin >> a[i];g&＃61;(g?gcd(g,a[i]):a[i]);}for(int i&＃61;1;i<&＃61;N;i&＃43;&＃43;) a[i]/&＃61;g,c[a[i]]&＃43;&＃43;,U&＃61;max(U,a[i]);for(int i&＃61;2,S&＃61;0;i<&＃61;U;i&＃43;&＃43;,S&＃61;0){if(!Flag[i])for(int j&＃61;i;j<&＃61;U;j&＃43;&＃61;i) S&＃43;&＃61;c[j],Flag[j]&＃61;1;Ans&＃61;max(Ans,S);}cout <<(Ans?N-Ans:-1) << endl;return 0;
}
D.Little C Loves 3 II
题意&＃xff1a;在一个网格图上放尽量多的点对&＃xff0c;使得每个点对的曼哈顿距离均为3
题解&＃xff1a;假设N 代码&＃xff1a; #include E.Region Separation 题意&＃xff1a;给定一颗点权树&＃xff0c;每次可以删除任意数量的边&＃xff0c;求每个联通块的点权和相同的切割方案。 题解&＃xff1a;挺神的一道题&＃xff0c;看了题解才会……假定限制了联通块的数量k&＃xff0c;令t&＃61;整棵树的点权和/k&＃xff0c;那么一个子树的点权和x对答案有贡献当且仅当t|x&＃xff0c;即(S/gcd(S,x))|k&＃xff0c;那么我们按照k分类求合法子树的数量。记c[k]表示树中点权和x满足&＃xff1a;S/gcd(S,x)为k的因子的子树的数量&＃xff08;即其对k的答案有贡献&＃xff09;&＃xff0c;假如c[i]>&＃61;i&＃xff0c;那么就存在分成i份的合法方案&＃xff0c;统计之。 代码&＃xff1a; #include
#include
#include
#include
#include
using namespace std;
#define ll long longll N,M;int main(){cin >> N >> M;if(N>M) swap(N,M);if(N&＃61;&＃61;1){if(M%6&＃61;&＃61;0) cout <
}
#include
#include
#include
#include
using namespace std;
#define ll long longconst int MAXN&＃61;1000000&＃43;2;
const ll MOD&＃61;1e9&＃43;7;
int N,p[MAXN];
ll s[MAXN],c[MAXN],f[MAXN],Ans;ll gcd(ll a,ll b){if(a<b) swap(a,b);return b?gcd(b,a%b):a;
}int main(){cin >> N;for(int i&＃61;1;i<&＃61;N;i&＃43;&＃43;) scanf("%lld",s&＃43;i);for(int i&＃61;2;i<&＃61;N;i&＃43;&＃43;) scanf("%d",p&＃43;i);for(int i&＃61;N;i;i--) s[p[i]]&＃43;&＃61;s[i];for(int i&＃61;N;i;i--){s[i]&＃61;s[1]/gcd(s[1],s[i]);if(s[i]<&＃61;N) c[s[i]]&＃43;&＃43;;}for(int i&＃61;N;i;i--)for(int j&＃61;2*i;j<&＃61;N;j&＃43;&＃61;i) c[j]&＃61;(c[j]&＃43;c[i])%MOD;f[1]&＃61;1;for(int i&＃61;1;i<&＃61;N;i&＃43;&＃43;)if(c[i]>&＃61;i)for(int j&＃61;2*i;j<&＃61;N;j&＃43;&＃61;i) f[j]&＃61;(f[j]&＃43;f[i])%MOD;for(int i&＃61;1;i<&＃61;N;i&＃43;&＃43;)if(c[i]>&＃61;i) Ans&＃61;(Ans&＃43;f[i])%MOD;cout <
}
京公网安备 11010802041100号