D
如果1/n是有限小数，不停乘以10，一定在有限次之后成为一个整数。
10的质因子只有2和5，只要保证分母的质因子只有2和5即可
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #define fo(i, l, r) for (long long i = l; i <= r; i++) #define fd(i, l, r) for (long long i = r; i >= l; i--) #define mem(x) memset(x, 0, sizeof(x)) #define ll long long #define ld double using namespace std; const int maxn = 150; const ll mod = 1e9 + 7; const double eps = 1e-9; ll read() { ll x = 0, f = 1; char ch = getchar(); while (!(ch >= '0' && ch <= '9')) { if (ch == '-') f = -1; ch = getchar(); }; while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }; return x * f; } int main() { int T,n; T=read(); while(T--){ n=read(); while(n%2==0)n/=2; while(n%5==0)n/=5; if(n>1){ printf("Yes\n"); }else{ printf("No\n"); } } return 0; }
F
仙人掌，环之间不相互影响，一个环至少删掉一条边，链无所谓，分别计算乘法原理合并
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #define fo(i, l, r) for (long long i = l; i <= r; i++) #define fd(i, l, r) for (long long i = r; i >= l; i--) #define mem(x) memset(x, 0, sizeof(x)) #define ll long long #define ld double using namespace std; const int maxn = 300500; const ll mod = 998244353; const double eps = 1e-9; ll read() { ll x = 0, f = 1; char ch = getchar(); while (!(ch >= '0' && ch <= '9')) { if (ch == '-') f = -1; ch = getchar(); }; while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }; return x * f; } vector<int> g[maxn]; int n,m; int d[maxn],rem; ll ans,pw[maxn*2]; void dfs(int u,int fa,int deep){ d[u] = deep; int v,sz=(int)g[u].size()-1; fo(i,0,sz){ v=g[u][i]; if(v==fa)continue; if(!d[v]) dfs(v,u,deep+1); else if(d[v]<d[u]){ ans=(ans*(pw[d[u]-d[v]+1]-1+mod))%mod; rem -= (d[u]-d[v]+1); } } } int main() { pw[0]=1;pw[1]=2; fo(i,2,500010) pw[i] = (pw[i-1]+pw[i-1])%mod; int u,v; while(scanf("%d%d",&n,&m)!=EOF){ ans=1; rem=m; fo(i,1,n){ d[i]=0; g[i].clear(); } fo(i,1,m){ u=read();v=read(); g[u].push_back(v); g[v].push_back(u); } fo(i,1,n){ if(!d[i]){ dfs(i,0,1); } } ans=(ans*pw[rem])%mod; printf("%lld\n",ans); } return 0; }
I
和之前做过的一个题很像，但是那个题需要贪心的性质为支撑，这个dp直接做就行了
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #define fo(i, l, r) for (long long i = l; i <= r; i++) #define fd(i, l, r) for (long long i = r; i >= l; i--) #define mem(x) memset(x, 0, sizeof(x)) #define ll long long #define ld double using namespace std; const int maxn = 100500; const ll mod = 998244353; const double eps = 1e-9; ll read() { ll x = 0, f = 1; char ch = getchar(); while (!(ch >= '0' && ch <= '9')) { if (ch == '-') f = -1; ch = getchar(); }; while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }; return x * f; } int n; int req[150][5]; char s[10][4]={"QQQ","QQW","QQE","WWW","QWW","WWE","EEE","QEE","WEE","QWE"}; char t[11] = "YVGCXZTFDB"; char a[maxn],b[maxn]; int dp[maxn][3][3][3],sum1[maxn][3][3],sum2[maxn][3],sum3[maxn],cnt[3]; int main() { fo(i,0,9){ fo(j,0,2){ if(s[i][j]=='Q')req[t[i]][0]++; if(s[i][j]=='W')req[t[i]][1]++; if(s[i][j]=='E')req[t[i]][2]++; } } while(scanf("%s",a+1)!=EOF){ n=strlen(a+1); int m = 0; fo(i,1,n){ if(a[i] != a[i-1]) b[++m] = a[i]; } swap(n,m); memset(dp,0x3f,sizeof(dp)); memset(sum1,0,sizeof(sum1)); memset(sum2,0,sizeof(sum2)); memset(sum3,0,sizeof(sum3)); int ans = mod; fo(i,1,n){ fo(t1,0,2){ fo(t2,0,2){ fo(t3,0,2){ cnt[0]=cnt[1]=cnt[2]=0; cnt[t1]++; cnt[t2]++; cnt[t3]++; if(cnt[0]!=req[b[i]][0]||cnt[1]!=req[b[i]][1]||cnt[2]!=req[b[i]][2])continue; dp[i][t1][t2][t3] = sum3[i-1]+3; if(sum1[i-1][t1][t2]) dp[i][t1][t2][t3] = min(dp[i][t1][t2][t3],sum1[i-1][t1][t2]+1); if(sum2[i-1][t1]) dp[i][t1][t2][t3] = min(dp[i][t1][t2][t3],sum2[i-1][t1]+2); if(!sum1[i][t2][t3] || (sum1[i][t2][t3] > dp[i][t1][t2][t3])){ sum1[i][t2][t3] = dp[i][t1][t2][t3]; } if(!sum2[i][t3] || (sum2[i][t3] > dp[i][t1][t2][t3])){ sum2[i][t3] = dp[i][t1][t2][t3]; } if(!sum3[i] || (sum3[i] > dp[i][t1][t2][t3])){ sum3[i] = dp[i][t1][t2][t3]; } if(i==n) ans=min(ans,dp[i][t1][t2][t3] + m); } } } } printf("%d\n",ans); } return 0; }
J
倒过来做kmp找循环节
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #define fo(i, l, r) for (long long i = l; i <= r; i++) #define fd(i, l, r) for (long long i = r; i >= l; i--) #define mem(x) memset(x, 0, sizeof(x)) #define ll long long #define ld double using namespace std; const int maxn = 10000500; const ll mod = 998244353; const double eps = 1e-9; ll read() { ll x = 0, f = 1; char ch = getchar(); while (!(ch >= '0' && ch <= '9')) { if (ch == '-') f = -1; ch = getchar(); }; while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }; return x * f; } int nxt[maxn]; void kmp_pre(char x[], int m, int next[]) { int i, j; j = next[0] =-1; i = 0; while (i < m) { while (-1 != j && x[i] != x[j]) j = next[j]; next[++i] = ++j; } } ll a, b,ans; char s[maxn], x[maxn]; int n, m; int main() { while (scanf("%lld%lld", &a, &b) != EOF) { scanf("%s", s + 1); n = strlen(s + 1); m = 0; fd(i, 1, n) { if (s[i] < '0' || s[i] > '9') break; x[++m] = s[i]; } kmp_pre(x+1,m,nxt); ans = a-b; fo(i,2,m){ ans=max(ans,a*i-b*(i-nxt[i])); } printf("%lld\n",ans); } return 0; }
A
直角三角形，就要看直角边在哪个点上，分两种情况讨论，然后围绕着直角点极角排序，找垂直的边。
#pragma GCC optimize(2) #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <stack> #include <vector> #include <set> #include <cmath> #include <queue> #include <map> #include <ctime> #define ll long long #define ld double #define lson rt << 1, l, m #define pi acos(-1) #define rson rt << 1 | 1, m + 1, r #define fo(i, l, r) for (int i = l; i <= r; i++) #define fd(i, l, r) for (int i = r; i >= l; i--) #define mem(x) memset(x, 0, sizeof(x)) #define eps 1e-7 using namespace std; const ll maxn = 4050; const ll mod = 998244353; ll read() { ll x = 0, f = 1; char ch = getchar(); while (!(ch >= '0' && ch <= '9')) { if (ch == '-') f = -1; ch = getchar(); }; while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }; return x * f; } struct Point { ll x, y; int isq,id; Point() {} Point(ll _x, ll _y) { x = _x; y = _y; } ll operator^(const Point &b) const { return x * b.y - y * b.x; } ll operator*(const Point &b) const { return x * b.x + y * b.y; } Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); } Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); } Point rotleft(){ return Point(-y,x); } Point rotright(){ return Point(y,-x); } int getfield(){ if(x>0&&y>=0)return 1; if(x<=0&&y>0)return 2; if(x<0&&y<=0)return 3; if(x>=0&&y<0)return 4; return 5; } } ns[maxn], tmp[maxn],qs[maxn], now; struct cmp { Point p; cmp(const Point &p0){p = p0;} bool operator()(const Point &aa,const Point &bb) { Point a = aa-p,b = bb-p; if(a.getfield() != b.getfield()){ return a.getfield() < b.getfield(); }else{ return (a^b)>0; } } }; int n, q; ll ans[maxn]; ll sum[maxn]; int main() { while (scanf("%d%d", &n, &q) != EOF) { mem(ans); fo(i, 1, n) { scanf("%lld%lld",&ns[i].x,&ns[i].y); ns[i].isq=0;ns[i].id=i; tmp[i]=ns[i]; } fo(i, 1, q) { scanf("%lld%lld",&qs[i].x,&qs[i].y); qs[i].isq=1;qs[i].id=i; now = qs[i]; sort(ns + 1, ns + 1 + n, cmp(now)); fo(j,1,n){ now=(ns[j]-qs[i]).rotleft(); now=qs[i]+now; int ret = upper_bound(ns+1,ns+1+n,now,cmp(qs[i])) - lower_bound(ns+1,ns+1+n,now,cmp(qs[i])); ans[i] += ret; } } fo(i,1,q){ ns[n+i]=qs[i]; } fo(i,1,n){ now = tmp[i]; sort(ns+1,ns+1+n+q,cmp(tmp[i])); fo(j,1,n+q){ if(!ns[j].isq&&ns[j].id!=now.id)sum[j]=sum[j-1]+1; else sum[j]=sum[j-1]; } fo(j,1,n+q){ if(!ns[j].isq)continue; now=(ns[j]-tmp[i]).rotleft(); now=tmp[i]+now; ans[ns[j].id] += sum[upper_bound(ns+1,ns+1+n+q,now,cmp(tmp[i]))-ns-1] - sum[lower_bound(ns+1,ns+1+n+q,now,cmp(tmp[i]))-ns-1]; now=(ns[j]-tmp[i]).rotright(); now=tmp[i]+now; ans[ns[j].id] += sum[upper_bound(ns+1,ns+1+n+q,now,cmp(tmp[i]))-ns-1] - sum[lower_bound(ns+1,ns+1+n+q,now,cmp(tmp[i]))-ns-1]; } } fo(i,1,q) printf("%lld\n",ans[i]); } return 0; }