A-An easy problem
直接输出
#include<bits/stdc++.h>
using namespace std;
int main(){
printf("Welcome to 17th NIT Programming Contest\n");
return 0;
} B-砍竹子 简单计数
每个正整数除2向下取整最后都会变成1，过程中不可能出现的数字最多只有log2(w)个（w为数字的值域，这log2(w)个互不相同）
所以所有可能出现的数字共有n*m*log2(w)个
用cnt[i]记录数字i在这n*m*log2(w)个中出现的次数，如果cnt[i]==n*m,就说嘛存在一种方案使得最后答案等于i。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010000;
int n,m,x,cnt[maxn],ans;
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d",&x);
assert(x<=1000000);
while(x){
if(++cnt[x]==n*m)
ans = max(ans,x);
x >>= 1;
}
}
}
printf("%d\n",ans);
return 0;
} C-折纸 bfs or 思维
显然的一点就是，如果n除去所有质因子2后无法整除a就是无法实现的
因为数据范围只有1e6所以直接bfs搜一遍即可
虽然一张纸上有很多折痕，但我们只需要最新制造的折痕即可
因为最优的方案不会在同一个折痕出操作两次，所以设状态x代表纸最新折痕在x处时的状态(显然x和n-x两状态是等价的)，用d[x]代表打到这个状态的最短路径长度(实际意义就是最少操作次数)
考虑当前状态为x。我们有两种决策。
1.把x这段对折，到达状态x/2.。（如果x为偶数）
2.把n-x这段对折，到达状态(n-x)/2。（如果n-x为偶数）
当然这题还有一个更加简单高效的做法
考虑倒推，如果有可行解，最终状态为a。（假设a<n-a）
那么上一个状态必然是2*a
然后依次类推，不断把短的那一段展开
知道回到初始状态n或者0
这一过程中展开的次数就是答案
可以证明这个算法的复杂度为log2(n)
另外如果有借的话，其实答案就是log2(lowbit(n)/lowbit(a))，如果n=a or n=0答案为0
因为每次乘2就相当于当前状态的lowbit*2
当前状态x变成n-x不会影响当前状态的lowbit
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a,b;
int main(){
scanf("%d%d",&n,&a);
int t = n;
while(t%2==0) t >>= 1;
if(a%t) { puts("-1"); return 0; }
int ans = 0;
while(a!=0&&a!=n){
if(a+a>n) a = n-a;
a = a+a,ans++;
}
printf("%d\n",ans);
return 0;
} #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
int n,a,b;
int d[maxn];
queue<int> que;
void solve(int n){
for(int i = 0; i <= n; i++) d[i] = 0;
d[0] = 1,que.push(0);
while(!que.empty()){
int u = que.front(); que.pop();
if(!(u%2)&&!d[u/2]){
d[u/2] = d[u]+1;
que.push(u/2);
}
if(!((n-u)%2)&&!d[(n-u)/2]){
d[(n-u)/2] = d[u]+1;
que.push((n-u)/2);
}
}
}
int main(){
scanf("%d%d",&n,&a); solve(n);
printf("%d\n",d[min(a,n-a)]-1);
return 0;
} D-盒中取球 思维and图的连通
把左右两边的边界看成点，边界与障碍物的距离就是横坐标之差的绝对值。障碍物之间的距离为欧几里得距离
如果障碍物之间或者障碍物与边界或者边界与边界的距离小于d，那么就给他们俩连一条边
如果最后两个边界代表的脸连通，说明小球无法取出，否则可以取出
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010;
int n,m,d,k,vis[maxn];
pair<int,int> p[maxn];
vector<int> G[maxn];
int dis_2(pair<int,int> a,pair<int,int> b){
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
void dfs(int u){
vis[u] = 1;
for(auto v : G[u])
if(!vis[v]) dfs(v);
}
int main(){
scanf("%d%d%d%d",&n,&m,&k,&d);
for(int i = 1,x,y; i <= k; i++){
scanf("%d%d",&x,&y);
p[i] = make_pair(x,y);
}
int s = k+1,t = k+2;
for(int i = 1; i <= k; i++){
if(p[i].first<d) G[s].push_back(i),G[i].push_back(s);
if(m-p[i].first+1<d) G[t].push_back(i),G[i].push_back(t);
for(int j = 1; j < i; j++){
if(dis_2(p[i],p[j])<d*d)
G[i].push_back(j),G[j].push_back(i);
}
}
dfs(s);
puts(vis[t]?"NO":"YES");
return 0;
} E-01串 贪心。
k为奇数时输出-1。
容易发现，若前k个位置确定下来，则整个串就确定了，因为对于任意两个下标i、j，若i % k == j % k，则s[i] == s[j]，所以我们只需要考虑前k个位置的取值。 对每个位置i，处理出两个值a[i]和b[i]分别表示这个位置为0和1需要修改的次数。
k为奇数时输出-1。
容易发现，若前k个位置确定下来，则整个串就确定了，因为对于任意两个下标i、j，若i % k == j % k，则s[i] == s[j]，所以我们只需要考虑前k个位置的取值。 对每个位置i，处理出两个值a[i]和b[i]分别表示这个位置为0和1需要修改的次数。
每个位置只能选择a和b其中一个，最终需要有k/2个a和k/2个b且和最小。按b-a升序排序，前k/2个取b，剩下的取a即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
int n,k,cnt[2][maxn];
char str[maxn];
vector<int> vec;
int main(){
scanf("%d%d%s",&n,&k,str+1);
if(k%2) { puts("-1"); return 0; }
for(int i = 1; i <= n; i++)
cnt[str[i]-'0'][i%k?i%k:k]++;
int ans = 0;
for(int i = 1; i <= k; i++) ans += cnt[1][i];
for(int i = 1; i <= k; i++) vec.push_back(cnt[0][i]-cnt[1][i]);
sort(vec.begin(),vec.end());
for(int i = 0; i+i <= k-1; i++) ans += vec[i];
printf("%d\n",ans);
return 0;
} F-Collecting stars思维。
1.首先最优解收集到的星星必然是连续的。如果存在一种隔开一个的收集方案，那必然存在更有解。
2.这一段连续的星星必然包含起点。
由上述两点我们可以知道，收集到的星星可以分为左边部分和右边部分。
所以就有了两种策略
1.先往左走收集星星最后再回到右边，往右走直到不能走为止。
2.先往右走收集星星最后再回到左边，往左走直到不能走为止。
如果不考虑返程，那肯定是每次往下一个跳即可，如果两个星星的
距离超出跳跃范围，那必然无法到达。
1.先往左走收集星星最后再回到右边，往右走直到不能走为止。
2.先往右走收集星星最后再回到左边，往左走直到不能走为止。
如果不考虑返程，那肯定是每次往下一个跳即可，如果两个星星的
距离超出跳跃范围，那必然无法到达。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
int n,m,s,a[maxn];
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i = 1; i <= n; i++) scanf("%d",a+i);
int r = 0,l = 0,ll = 0,rr = 0;
for(int i = s; i < n; i++){
if(a[i+1]-a[i]>m) break;
r++;
}
for(int i = s; i > 1; i--){
if(a[i]-a[i-1]>m) break;
l++;
}
for(int i = s; i > 1&&i < n; i++){
if(a[i+1]-a[i-1]>m) break;
rr++;
}
for(int i = s; i > 1&&i < n; i--){
if(a[i+1]-a[i-1]>m) break;
ll++;
}
printf("%d\n",max(rr+l,r+ll)+1);
return 0;
} G-等差数列暴力。
假设当前有一个长度为五的等差数列a[1],a[2], a[3], a[4], a[5]。
如果确定a[2l, a[4]即可确定a[1], a[3], a[5]。
所以这题直接枚举第二项和第四项。维护一个前缀一个后缀还有两项中间各三个桶记录中间每个数字出现的次数，然后统计当前的贡献即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010,N = 1e6+10;
int n,a[maxn],pre[N],suf[N],ins[N];
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",a+i);
ll ans = 0;
pre[a[1]]++,ins[a[3]]++;
for(int i = 5; i <= n; i++) suf[a[i]]++;
for(int i = 2; i <= n-3; i++){
for(int j = i+2; j <= n-1; j++){
if((a[j]-a[i])%2==0){
int d = (a[j]-a[i])/2;
if(a[i]-d>=1&&a[i]-d<=1000000&&a[j]+d>=1&&a[j]+d<=1000000)
ans += pre[a[i]-d]*ins[a[i]+d]*suf[a[j]+d];
}
ins[a[j]]++,suf[a[j+1]]--;
}
for(int j = i+2; j <= n-1; j++)
ins[a[j]]--,suf[a[j+1]]++;
pre[a[i]]++,ins[a[i+1]]--,ins[a[i+2]]++,suf[a[i+3]]--;
}
printf("%lld\n",ans);
return 0;
} H-最小公倍数最大集 简单数论
首先集合中肯定可以塞一个n，然后其他数字必然是n的因子。考虑其他数字是n除去一些质因子
如果当前集合中某个数字中质因子p1,p2的指数都小于n中p1，p2的指数。那么之后放入集合的数字中质因子p1,p2不能缺少
所以最优解就是，每个数字都是n除去某个质因子
所以答案就是n的质因子种类数+1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,ans=1;
int main(){
scanf("%lld",&n);
for(ll i = 2; i*i <= n; i++){
if(n%i==0) ans++;
while(n%i==0) n /= i;
}if(n>1) ans++;
printf("%lld\n",ans==1?0:ans);
return 0;
} I-密码破译 签到题。
按题意模拟即可。
注意解决两个加密问题的顺序要反过来。
先栅栏加密，再恺撒加密。
按题意模拟即可。
注意解决两个加密问题的顺序要反过来。
先栅栏加密，再恺撒加密。
#include<bits/stdc++.h>
using namespace std;
string Caesar(string c, int x)
{
for (int i = 0; i < c.length(); ++i)
c[i] = ((c[i] - 'a' - x + 26) % 26) + 'a';
return c;
}
string Fence(string c)
{
string a = "", b = "";
for (int i = 0; i < c.length(); ++i)
{
if (i % 2) a += c[i];
else b += c[i];
}
return b + a;
}
int main()
{
int T, x;
string c;
cin >> T;
while (T--)
{
cin >> c;
cin >> x;
c = Fence(c);
c = Caesar(c, x);
cout << c << endl;
}
return 0;
} J-关灯 递推。
设f[i]为i栈灯亮着时关完所有灯的期望次数，可以列出方程组：
f[0]=0;
f[i]=i/n*f[i-1]+(n-i)/n*f[i+1]+1;
f[n]=f[n-1]+1;
解方程组即可。
可以自下往上把每个f[i]的f[i+1]消掉。
再自上往下就可以求出所有答案。
设f[i]为i栈灯亮着时关完所有灯的期望次数，可以列出方程组：
f[0]=0;
f[i]=i/n*f[i-1]+(n-i)/n*f[i+1]+1;
f[n]=f[n-1]+1;
解方程组即可。
可以自下往上把每个f[i]的f[i+1]消掉。
再自上往下就可以求出所有答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e6+10;
ll qpow(ll a,ll b,ll mod){
ll ans;
// a%=mod;
ans=1;
while(b!=0)
{
if(b&1)
ans=(ans*a)%mod;
b/=2;
a=(a*a)%mod;
}
return ans;
}
ll inv(ll x){return qpow(x,mod-2,mod);}
signed main()
{
int n,k;
cin>>n>>k;
ll ans=1,c=1;
static int res[N];
res[n]=1;
for(int i=n-1;i>=1;--i)
{
ll pc=c;
c=(pc*(n-i)%mod*inv(n)%mod+1)*n%mod*inv(i)%mod;
res[i]=(1ll*(n-i)*pc%mod+n)%mod*inv(i)%mod;
ans=(ans+res[i])%mod;
}
for(int i=n;i>k;--i)ans=(ans-res[i]+mod)%mod;
cout<<ans<<endl;
return 0;
}
/**************************************************************************************/ K-Boring Array 并查集 and set。
考虑一开始数组所有的数都是不可见的。
然后按数字从小到达一一激活，如果当前被激活的数字的两边都有被激活的数字或者有一边有，那就说明这两个或者三个段可以合并起来。(可以用并查集维护这些段)。
考虑一开始数组所有的数都是不可见的。
然后按数字从小到达一一激活，如果当前被激活的数字的两边都有被激活的数字或者有一边有，那就说明这两个或者三个段可以合并起来。(可以用并查集维护这些段)。
假设当前枚举到数字x时，当前的集合内元素种类等于x时，可以把当前段的长度用来更新答案。
在维护并查集的同时再维护一个集合内数字个数，种类数可以用STL的set维护，合并时用启发式合并即可,复杂度为o(n log2 n)，当然可以用可持久化线段树求解区间种类数将复杂度优化到o(n log n)。
在维护并查集的同时再维护一个集合内数字个数，种类数可以用STL的set维护，合并时用启发式合并即可,复杂度为o(n log2 n)，当然可以用可持久化线段树求解区间种类数将复杂度优化到o(n log n)。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n,a[maxn],pre[maxn],Size[maxn],ans;
set<int> Set[maxn];
vector<int> pos[maxn];
int find(int x){ return pre[x]==x?x:pre[x]=find(pre[x]); }
bool merge(int x,int y,int z){
x = find(x),y = find(y);
if(x==y) return false;
else{
if(Set[x].size()>Set[y].size()) swap(x,y);
for(auto p : Set[x]) Set[y].insert(p);
Size[y] += Size[x],pre[x] = y;
if(Set[y].size()==z) ans = max(ans,Size[y]);
return true;
}
}
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",a+i);
for(int i = 1; i <= n; i++) pos[a[i]].push_back(i);
for(int i = 1; i <= n; i++) pre[i] = i,Size[i] = 1;
for(int i = 1; i <= n; i++){
for(auto x : pos[i]){
Set[x].insert(i);
if(Set[x].size()==i) ans = max(ans,i);
if(!Set[x-1].empty()) merge(x,x-1,i);
if(!Set[x+1].empty()) merge(x,x+1,i);
}
}
printf("%d\n",ans);
return 0;
} L-Triangle Numbers 数位DP。
首先考虑如何确定单个数字是否是“Triangle Numbers”
接下来是最关键的，如何将搜索记忆化。即考虑这样的情况，当前已经枚举一些高位（或者说已经确定数字的前缀），剩下一些低位（后缀）还没有枚举，且这些低位的枚举没有限制，每一位都可以是0-9的任意一个。
首先考虑如何确定单个数字是否是“Triangle Numbers”
接下来是最关键的，如何将搜索记忆化。即考虑这样的情况，当前已经枚举一些高位（或者说已经确定数字的前缀），剩下一些低位（后缀）还没有枚举，且这些低位的枚举没有限制，每一位都可以是0-9的任意一个。
—个简单直观的想法是以0-9这十种数字的出现次数和可枚举的后缀长度作为前缀等价类的划分依据。
被划分至同一个等价类的前缀关于“有多少个Triangle Numbers"的问题具有一致的答案，一个等价类只需要暴力计算一次结果并将结果记录到记忆化数组中，之后在遇到直接根据记忆化数组返回结果即可。
基于这个想法和本题的数据范围，需要开辟大约10*.1010的空间用于存储每个状态(等价类)的结果，显然开不下这样的空间。
被划分至同一个等价类的前缀关于“有多少个Triangle Numbers"的问题具有一致的答案，一个等价类只需要暴力计算一次结果并将结果记录到记忆化数组中，之后在遇到直接根据记忆化数组返回结果即可。
基于这个想法和本题的数据范围，需要开辟大约10*.1010的空间用于存储每个状态(等价类)的结果，显然开不下这样的空间。
考虑放宽等价类的划分依据，实际上某个数字X出现3次以上都可以当作它出现了3次，因为X在某个合法三角形中最多出现3次。
这样每个数字的只有0,1，2，3四种情况，容易想到四进制状态压缩来保存每个数字的出现次数。
这样空间就变成了10* 4^10 = 10485760。
这样每个数字的只有0,1，2，3四种情况，容易想到四进制状态压缩来保存每个数字的出现次数。
这样空间就变成了10* 4^10 = 10485760。
#include<bits/stdc++.h>
using namespace std;
inline bool read(int& x){return ~scanf("%d", &x);}
inline bool read(long long & x) { return ~scanf("%lld", &x); }
template<typename T1, typename ...T2>
inline bool read(T1 &x,T2 &...y) {
return read(x) && read(y...);
}
int num[200];
bool check(int a,int b,int c)
{
int v[] = { a,b,c };
sort(v, v + 3);
return v[0] +v[1] > v[2];
}
int tmpNum[200];
bool checkNum(int x)
{
int bit = 0;
while (x)
{
tmpNum[++bit] =x % 10;
x /= 10;
}
for (int i = 1; i <= bit; i++)
{
for (int j = i + 1; j <= bit; j++)
{
for (int k = j + 1; k <= bit; k++)
{
if (check(tmpNum[i], tmpNum[j], tmpNum[k]))return 1;
}
}
}
return 0;
}
int dp[11][1048576+1000];
int pow4[200];
int cnt[100];
int dfs(int pos,bool limit,bool zero,int sta,int now)
{
if (pos == 0) {
//cerr << now << " " << checkNum(now) << endl;
return checkNum(now);
}
if (!limit &&!zero && ~dp[pos][sta])
return dp[pos][sta];
int res = 0;
int up = limit ?num[pos]:9;
for (int i = 0; i <= up; i++)
{
int tmpc = cnt[i];
int nxsta = sta;
if (!( zero && i == 0 )) {
if (cnt[i] < 3) {
nxsta += pow4[i];
}
cnt[i]++;
}
res += dfs(pos - 1, limit && i == up, zero && i == 0, nxsta, now * 10 + i);
cnt[i] = tmpc;
}
if (!limit && !zero)
dp[pos][sta] = res;
return res;
}
int solve(int x)
{
if (x < 0)return 0;
int bit = 0;
while (x)
{
num[++bit] = x % 10;
x /= 10;
}
return dfs(bit, true, true, 0, 0);
}
int main()
{
#ifdef LOCAL
//freopen("1.in", "r", stdin);
//freopen("2.out", "w", stdout);
#endif
//cout << checkNum(345) << endl;
pow4[0] = 1;
pow4[1] = 4;
for (int i = 2; i < 12; i++) {
pow4[i] = pow4[i-1] * 4;
}
memset(dp, -1, sizeof(dp));
int t;
read(t);
while (t--)
{
int l, r;
read(l, r);
//cerr << solve(r) << " " << solve(l - 1) << endl;
int ans = solve(r) -solve(l - 1);
printf("%d\n", ans);
}
return 0;
} 
全部评论
(1) 回帖