using namespace std;
char a[1000005];
int main()
{
cin >> a;
int len = strlen(a);
for(int i=0; i
if(a[i] == 'r')
cout << i+1 << endl;
}
for(int i=len-1; i>=0; i--)
{
if(a[i] == 'l')
cout << i+1 << endl;
}
return 0;
}
#include
#include
#include
#include
#include
using namespace std;
char a[1000005];
int main()
{
cin >> a;
int len = strlen(a);
for(int i=0; i
if(a[i] == 'r')
cout << i+1 << endl;
}
for(int i=len-1; i>=0; i--)
{
if(a[i] == 'l')
cout << i+1 << endl;
}
return 0;
}
I. Good Sequences
此题直接用o(n^2)的dp铁定超时，但还是忍不住交了一发
参考了CF的代码，预先将所有不互质的关系保存好。然后从遍历，dp[i] = max(dp[p[i][j]]+1,dp[i])
[cpp]
#include
#include
#include
#include
#include
#include
using namespace std;
int a[100005],good[100005],dp[100005];
int n;
vector
int main()
{
int i,j;
while(cin >> n)
{
int maxn = 0;
memset(good,0,n);
memset(dp,0,sizeof(dp));
for(i=0; i
scanf("%d",&a[i]);
maxn = max(a[i],maxn);
good[a[i]] = 1;
}
for(i=2; i<=maxn; i++)
{
int tmp = 0;
for(j=i; j<=maxn; j+=i)
{
if(good[j] == 1)
{
if(tmp != 0)
p[j].push_back(tmp);
tmp = j;
}
}
}
int ans = 1;
for(i=2; i<=maxn; i++)
{
if(good[i] == 1)
{
dp[i] = 1;
for(j=0; j
dp[i] = max(dp[p[i][j]]+1,dp[i]);
}
ans = max(dp[i],ans);
}
}
cout << ans << endl;
}
return 0;
}
#include
#include
#include
#include
#include
#include
using namespace std;
int a[100005],good[100005],dp[100005];
int n;
vector
int main()
{
int i,j;
while(cin >> n)
{
int maxn = 0;
memset(good,0,n);
memset(dp,0,sizeof(dp));
for(i=0; i
scanf("%d",&a[i]);
maxn = max(a[i],maxn);
good[a[i]] = 1;
}
for(i=2; i<=maxn; i++)
{
int tmp = 0;
for(j=i; j<=maxn; j+=i)
{
if(good[j] == 1)
{
if(tmp != 0)
p[j].push_back(tmp);
tmp = j;
}
}
}
int ans = 1;
for(i=2; i<=maxn; i++)
{
if(good[i] == 1)
{
dp[i] = 1;
for(j=0; j
dp[i] = max(dp[p[i][j]]+1,dp[i]);
}
ans = max(dp[i],ans);
}
}
cout << ans << endl;
}
return 0;
}