#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include<stack> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 8e4 + 10; int main() { ll n,s; cin >> n >> s; ll tmp = ceil(s * 1.0 / (n * 1.0 )); printf("%lld\n",tmp); }
CodeForces - 1061B
题意：n列，原来每列都放有a[ i ] 个盒子，问最多能移除多少个盒子后，使移除后的俯视图和右视图与移除前的相同
题解：每一列尽可能的只拿最上面的一个，接下来的剩下的在最高的一列拿，遍历一下就好了
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include<stack> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 1e5 + 10; ll a[maxn]; int main() { ll n,m; scanf("%lld %lld",&n,&m); ll maxx = -1; ll sum = 0; for(int i=0;i<n;i++) { scanf("%lld",&a[i]); maxx = max(maxx,a[i]); sum += a[i]; } sort(a,a+n); int ans = 0; ll pos = 1; for(int i=0;i<n;i++) { if(a[i] >= pos) { ans++; pos++; } else { ans++; } } pos--; maxx = max(0LL,maxx - pos); // cout<<maxx<<endl; printf("%lld\n",sum - (ans + maxx)); }
CodeForces - 1061C
题意：给出序列ai，询问有多少个 a 的子序列 b 满足，对于任意的b[i]，b[i] mod i = 0
题解：先预处理因子，将每一个的倍数处理出来。之后开始dp累加前一个的方案数
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include<stack> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const int mod = 1e9 + 7; int n,a[maxn],dp[maxn * 10],ans; vector<int>fact[maxn * 10]; int maxx = -1; int main() { scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); maxx = max(maxx,a[i]); } for(int i = 1; i <= maxx; i++) for(int j = 1; j <= maxx / i; j++) fact[i * j].push_back(i); for(int i = 1; i <= n; i++) sort(fact[a[i]].begin(),fact[a[i]].end()); dp[0] = 1; for(int i = 1; i <= n; i++) { for(int j = fact[a[i]].size() - 1; j >= 0; j--) { int x = fact[a[i]][j]; dp[x] += dp[x - 1]; dp[x] %= mod; //printf("i = %d dp[%d] = %d\n",i,x,dp[x]); } } for(int i = 1; i <= n; i++) { ans += dp[i]; ans %= mod; } printf("%d\n",ans); }
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include<stack> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 1e5 + 10; vector<int>g[maxn]; vector<int>path; int vis[maxn][2]; int st[maxn]; int n,m; bool circle = false; void dfs(int x,int dep) { if(vis[x][dep & 1]) //vis的后面：1代表奇数步可达，0代表偶数不可达 return; vis[x][dep & 1] = 1; if(g[x].size() == 0 && (dep & 1)) { puts("Win"); for(int i = 0; i < path.size(); i++) printf("%d%c",path[i],i == path.size() - 1 ? ‘\n‘ : ‘ ‘); exit(0); } for(int i = 0; i < g[x].size(); i++) { int next = g[x][i]; if(st[next]) circle = true; path.push_back(next); st[next] = true; dfs(next,dep + 1); path.pop_back(); st[next] = false; } } int main() { scanf("%d %d",&n,&m); int tmp,u; for(int i = 1; i <= n; i++) { scanf("%d",&tmp); while(tmp--) { scanf("%d",&u); g[i].push_back(u); } } int start; scanf("%d",&start); st[start] = true; path.push_back(start); dfs(start,0); if(circle) puts("Draw"); else puts("Lose"); }
原文：https://www.cnblogs.com/smallhester/p/11178065.html
