Round #460 C. Seat Arrangements 题意：给定一个由’*’和’.’组成的二维数组，问这之中能够找出多少连续的k个’.’。 题解：要求找连续的k个’.’，那么如果存在连续的p个’.’，就能找出p-k+1个要求的子串。只需对每一行与每一列处理找出所有连续的’.’即可。
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<queue> #include<map> #include<vector> #include<iostream> #include<algorithm> #define maxn 2050 #define INF 0x3f3f3f3f using namespace std; typedef long long ll; int n,m,k; char s[maxn][maxn],e[maxn][maxn]; char t[maxn],tmp[maxn]; bool judge(int i,int j) { for(int p=0;p<k;p++) { if(s[i][j+p]!='.') return false; } return true; } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=0;i<n;i++) scanf("%s",s[i]); int ans=0; for(int i=0;i<n;i++) { int j=0; while(j<m) { if(s[i][j]!='.') { j++; continue; } int num=0; while(s[i][j]=='.') { num++; j++; } if(num>=k) ans+=(num-k+1); } } for(int i=0;i<m;i++) { int j=0; while(j<n) { if(s[j][i]!='.') { j++; continue; } int num=0; while(s[j][i]=='.') { num++; j++; } if(num>=k) ans+=(num-k+1); } } if(k==1) ans/=2; printf("%d\n",ans); return 0; }Round #460 D. Substring 题意：定义一个字符串的权值为串中出现次数最多的字符出现的次数。现在在字符串的一些点之间连有向边，要求找一条路径使得这条路径的权值最大。若最大权值为无穷大，则输出-1。 题解：权值为无穷大的情况即为有向图中存在环。因此可以用拓扑排序判断图中是否存在环，在拓扑排序中用dp[i][j]维护以第i个字符结尾，字母j出现的最多次数。用链式前向星存图，每遍历到一个字符，就进行状态转移更新dp值。若一条边为从u到v，则： dp[v][j]=max(dp[v][j],dp[u][j]+(s[v]-j==’a’))。
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<queue> #include<map> #include<vector> #include<iostream> #include<algorithm> #define maxn 300050 #define INF 0x3f3f3f3f #define eps 1e-8 using namespace std; typedef long long ll; int n,m,a,b,num,no; int in[maxn],head[maxn]; int dp[maxn][26]; char s[maxn]; struct node { int to; int nxt; }e[maxn]; void tuopu() { queue<int>q; for(int i=1;i<=n;i++) { if(!in[i]) { q.push(i); dp[i][s[i]-'a']=1; } } while(!q.empty()) { int u=q.front(); q.pop(); num++; for(int i=head[u];i!=-1;i=e[i].nxt) { int v=e[i].to; for(int j=0;j<26;j++) dp[v][j]=max(dp[v][j],dp[u][j]+(s[v]==j+'a')); in[v]--; if(!in[v]) q.push(v); } } } int main() { no=num=0; scanf("%d%d",&n,&m); scanf("%s",s+1); memset(in,0,sizeof(in)); memset(head,-1,sizeof(head)); for(int i=0;i<m;i++) { scanf("%d%d",&a,&b); in[b]++; e[no].to=b; e[no].nxt=head[a]; head[a]=no++; } tuopu(); if(num!=n) printf("-1\n"); else { int ans=0; for(int i=1;i<=n;i++) { for(int j=0;j<26;j++) ans=max(ans,dp[i][j]); } printf("%d\n",ans); } return 0; }Educational Round 37 B. Tea Queue 题意：n个人排队喝茶，每个人喝茶需要一分钟，并各自有一个等待的时间区间。问每个学生喝到茶的时刻是多少，若喝不到茶则输出0。 题解：对于每个学生比较一下当前时间和其等待的时间区间。若当前时间在区间内则输出当前时间并加一，若当前时间小于区间下限则当前时间加一再比较，若当前时间大于区间上限则输出0。
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<queue> #include<map> #include<vector> #include<iostream> #include<algorithm> #define maxn 1050 #define INF 0x3f3f3f3f #define eps 1e-8 using namespace std; typedef long long ll; int t, n, l, r; int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); int ans = 0; for (int i = 0; i < n; i++) { scanf("%d%d", &l, &r); ans = max(ans, l); if (ans > r) printf("0"); else { printf("%d", ans); ans++; } printf(i == n - 1 ? "\n" : " "); } } return 0; }Educational Round 37 C. Swap Adjacent Elements 题意：给出一个长度为n的数列，现在指定这个数列的若干位可以将其与下一位进行交换。问能否通过若干次变换将数列变为有序的。 题解：如果连续的若干个位置都可以交换，那么这一段子序列必定可以变为有序。将所有这种的子序列都变为有序的，然后判断此时的数列是否为有序的即可。
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<string> #include<queue> #include<map> #include<vector> #include<iostream> #include<algorithm> #include<iomanip> #define maxn 200050 #define INF 0x3f3f3f3f #define eps 1e-301 const double pi=acos(-1.0); using namespace std; typedef long long ll; typedef long double ld; const int mod=1000000007; int n,a[maxn]; char s[maxn]; int main() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); scanf("%s",s); int cnt=0,l,r; while(cnt<n-1) { if(s[cnt]=='0') { cnt++; continue; } if(s[cnt]=='1') { l=cnt; while(s[cnt]=='1') cnt++; r=cnt; sort(a+l,a+r+1); } } for(int i=0;i<n;i++) { if(a[i]!=i+1) { printf("NO\n"); return 0; } } printf("YES\n"); return 0; }Educational Round 37 F. SUM and REPLACE 题意：定义D(x)为x的因数数目，现在给定一个数列需要支持以下两种操作：将数列的给定区间变为其D值；求数列给定区间的和。 题解：题目给定的范围内，所有大于1的数在进行最多6次取D值操作后都会变成2。先预用筛法处理出1e6范围内的D值，然后构造一棵线段树维护区间之和与区间最大值。每次更新时暴力搜至树的底部，若区间最大值小于等于2则不必再进行更新。
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<string> #include<queue> #include<map> #include<vector> #include<iostream> #include<algorithm> #include<iomanip> #define maxn 300050 #define maxm 1000050 #define INF 0x3f3f3f3f #define eps 1e-8 const double pi=acos(-1.0); using namespace std; typedef long long ll; typedef long double ld; int n,m,s,x,y,no,a[maxn]; ll tree[maxn*4],maxx[maxn*4]; ll num[maxm]; ll Max(ll a,ll b) { return a>b?a:b; } void build(int root,int l,int r) { if(l==r) { tree[root]=maxx[root]=a[l]; return; } int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); tree[root]=tree[root*2]+tree[root*2+1]; maxx[root]=Max(maxx[root*2],maxx[root*2+1]); } void update(int root,int l,int r,int aiml,int aimr) { if(l>aimr||r<aiml||maxx[root]<=2) return; if(l==r) { tree[root]=maxx[root]=num[maxx[root]]; return; } int mid=(l+r)/2; if(r<=mid)update(root*2,l,mid,aiml,aimr); else if(l>mid)update(root*2+1,mid+1,r,aiml,aimr); else { update(root*2,l,mid,aiml,aimr); update(root*2+1,mid+1,r,aiml,aimr); } tree[root]=tree[root*2]+tree[root*2+1]; maxx[root]=Max(maxx[root*2],maxx[root*2+1]); } ll query(int root,int l,int r,int aiml,int aimr) { if(l>=aiml&&r<=aimr) return tree[root]; if(l>aimr||r<aiml) return 0; int mid=(l+r)/2; return query(root*2,l,mid,aiml,aimr)+query(root*2+1,mid+1,r,aiml,aimr); } int main() { memset(num,0,sizeof(num)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<maxm;i++) { for(int j=i;j<maxm;j+=i) num[j]++; } build(1,1,n); for(int i=0;i<m;i++) { scanf("%d%d%d",&s,&x,&y); if(s==1) update(1,1,n,x,y); else if(s==2) printf("%I64d\n",query(1,1,n,x,y)); } return 0; }