[뉴커우 OI 주간 경기 15-보급팀] A [시뮬레이션] B [DP] D [이산화+DP+트리 수조]
44609 단어 이산화항상 안 되는 DP.트리 배열
문서 목록
A
문제: 길이가 n인 문자열이 완전히 여러 mq 연결으로 구성되었는지: 시뮬레이션이 이루어졌습니다.#include
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;
char s[N];
int main(int argc, char **args){
// freopen("in.txt", "r", stdin);
int q; cin >> q;
while(q--){
scanf("%s", s);
int cur = 0;
bool flag = true;
for(int i = 0; s[i]; i++){
if( (cur == 1 && s[i] == 'q' )|| (cur == 0 && s[i] == 'm'))
cur = cur ^ 1;
else
flag = false;
}
puts((flag && !cur) ? "Yes":"No");
}
return 0;
}
B
사고방식: 시합할 때 검색+가지치기만 생각했어. 이러면 틀림없어. 50% 데이터만 넘었어.시합 후에 다시 생각해 보니 DP를 고려할 수 있었다. n개의 보물과 최대가 10000이기 때문에 앞의 k개의 최소치를 취하면 된다. 이때 만약에 미리 처리하고 i를 위한 방안의 수를 처리할 수 있다면 문제가 해결될 것이다.그래서 DP, dp[i][j]가 앞의 i개 보물의 합을 j로 하는 방안을 고려했다.점차적 방정식: dp [i] [j+a ik] = ∑k = 1m i ∑j = 0 10000: a i k d p [i-4-1] [j] dp[i] [j+a {ik}] =\sum{k=1}^{m_i}\sum_{j=0}^{10000-a {ik}}}dp[i-1][j]dp[i][j+aik]=k=1∑mij=0∑10000--aikdp[i-1][j]시간 복잡도가 o(1e8)인 것을 발견하여 시간이 지나갈 수 없을 것 같지만 이 코드의 구조가 간단하고 간결하기 때문에 상수가 매우 작기 때문에 사실상 시간적으로 지나갈 수 있다(그리고 우객 평가기 1s는 많이 달렸을 것이다. 적어도 1e8안은 충분할 것 같다).공간적으로 i층은 i-1층의 값만 사용하기 때문에 스크롤 그룹을 이용하여 1차원을 최적화할 수 있다.검색 코드:#include
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;
int n, k;
priority_queue <int,vector<int>,less<int> > qu;
vector<int>ve[N];
void DFS(int now, int sum){
if(qu.size() >= k && sum >= qu.top()) return; //
// cout << now <
if(now == n + 1) {
if(qu.size() < k)
qu.push(sum);
else {
if(qu.top() > sum) {
qu.pop(); qu.push(sum);
}
}
return;
}
for(int i = 0; i < ve[now].size(); i++){
int v = ve[now][i];
DFS(now + 1, sum + v);
}
}
int main(int argc, char **args){
// freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &k);
for(int i = 1; i <= n ;i++){
int m; scanf("%d", &m);
while(m--){
int a; scanf("%d", &a); ve[i].push_back(a);
}
sort(ve[i].begin(), ve[i].end());
}
DFS(1, 0);
int ans = 0;
while(k--){
// cout << qu.top() <
ans += qu.top(); qu.pop();
}
printf("%d
", ans);
return 0;
}
DP 코드#include
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;
ll dp[N][2];
int main(int argc, char **args){
// freopen("in.txt", "r", stdin);
int n, k; scanf("%d%d", &n, &k);
int cur = 0; dp[0][cur ^ 1] = 1;
for(int i = 1; i <= n; i++){
int m; scanf("%d", &m);
for(int j = 0; j <= 10000; j++) dp[j][cur] = 0;
while(m--){
int a; scanf("%d", &a);
for(int j = 0; j <= 10000; j++){
if(dp[j][cur ^ 1] > 0)
dp[j + a][cur] += dp[j][cur ^ 1];
}
}
cur ^= 1;
}
cur ^= 1;
int ans = 0;
for(int i = 1; i <= 10000; i++){
if(k > 0) {
if(dp[i][cur] >= k) {
ans += k * i;
}else {
ans += dp[i][cur] * i;
}
k -= dp[i][cur];
}else break;
}
printf("%d
", ans);
return 0;
}
D
사고방식: 시합 때의 사고방식이 맞았는데 아쉽게도 버그를 발견하지 못했다.사실은 매우 간단하다. 이원조에서 삼원조로 가는 과정에서 우리는 계발을 얻을 수 있다.뒤에 m원조까지 확장되었는데 사실 본질은 모두 같다.dp[i][j]를 고려하면 위치 j로 시작한 i의 원조 개수를 나타낸다.전이 방정식: dp[i] [j] = ∑ak > a i & k > i dp [i -3 1] [k] dp[i] [j] =\sum{a k>a i\&k>i}dp[i-1][k]dp[i][j]=ak>ai&k>i ∑dp[i-3-1][k]는 어떻게 오른쪽 식을 구하는지 나무형 수조로 고려할 수 있습니다.트리 배열을 사용하려면 a i ai ai 값은 배열로 표시하지만 원래 a i ai ai의 값이 매우 커서 본 문제와 a i a 를 발견하였다iai는 본래 값과 상관없이 원소 간의 상대적인 크기가 변하지 않으면 되기 때문에 이산화한다.동시에 식자를 관찰하면 현재 층은 전 층의 값만 사용할 수 있기 때문에 스크롤 그룹을 이용하여 공간을 최적화할 수 있다.
코드:#include
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;
int n, m, nn;
int sum[N];
int c[N * 4], a[N];
void add(int pos, int x){
for(pos; pos > 0; pos -= (pos & -pos)){
c[pos] = (c[pos] + x) % MOD;
}
}
int query(int pos){
int sum = 0;
for(pos ; pos <= nn; pos += (pos & -pos)){
sum = (sum + c[pos]) % MOD;
}
return sum;
}
vector<int>ve;
int main(int argc, char **args){
// freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]); ve.push_back(a[i]);
}
sort(ve.begin(), ve.end());
ve.erase(unique(ve.begin(), ve.end()), ve.end());
for(int i = 1; i <= n; i++){
a[i] = lower_bound(ve.begin(), ve.end(), a[i]) - ve.begin() + 1; // ,
sum[i] = 1;//
}
nn = n * 2;
for(int j = 2; j <= m; j++){
memset(c, 0, sizeof(c));
for(int i = n; i > 0; i--){
add(a[i] , sum[i]);
sum[i] = query(a[i] + 1);
// cout << sum[i] <
}
}
if(m == 1){
cout << n <<"
";
}else {
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = (ans + sum[i]) % MOD;
}
printf("%d
", ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[NOIP2015 시뮬레이션 11.2만] 배미표
Description
Alice와 Bob, 아뇨, CZL과 YYY가 게임을 하고 있어요.책상 위에 n장의 카드가 있는데, 한 장의 카드는 두 사람에게 각각 유혹의 가치와 그 자신의 가치를 가지고 있다.CZL이 먼저 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;
char s[N];
int main(int argc, char **args){
// freopen("in.txt", "r", stdin);
int q; cin >> q;
while(q--){
scanf("%s", s);
int cur = 0;
bool flag = true;
for(int i = 0; s[i]; i++){
if( (cur == 1 && s[i] == 'q' )|| (cur == 0 && s[i] == 'm'))
cur = cur ^ 1;
else
flag = false;
}
puts((flag && !cur) ? "Yes":"No");
}
return 0;
}
사고방식: 시합할 때 검색+가지치기만 생각했어. 이러면 틀림없어. 50% 데이터만 넘었어.시합 후에 다시 생각해 보니 DP를 고려할 수 있었다. n개의 보물과 최대가 10000이기 때문에 앞의 k개의 최소치를 취하면 된다. 이때 만약에 미리 처리하고 i를 위한 방안의 수를 처리할 수 있다면 문제가 해결될 것이다.그래서 DP, dp[i][j]가 앞의 i개 보물의 합을 j로 하는 방안을 고려했다.점차적 방정식: dp [i] [j+a ik] = ∑k = 1m i ∑j = 0 10000: a i k d p [i-4-1] [j] dp[i] [j+a {ik}] =\sum{k=1}^{m_i}\sum_{j=0}^{10000-a {ik}}}dp[i-1][j]dp[i][j+aik]=k=1∑mij=0∑10000--aikdp[i-1][j]시간 복잡도가 o(1e8)인 것을 발견하여 시간이 지나갈 수 없을 것 같지만 이 코드의 구조가 간단하고 간결하기 때문에 상수가 매우 작기 때문에 사실상 시간적으로 지나갈 수 있다(그리고 우객 평가기 1s는 많이 달렸을 것이다. 적어도 1e8안은 충분할 것 같다).공간적으로 i층은 i-1층의 값만 사용하기 때문에 스크롤 그룹을 이용하여 1차원을 최적화할 수 있다.검색 코드:
#include
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;
int n, k;
priority_queue <int,vector<int>,less<int> > qu;
vector<int>ve[N];
void DFS(int now, int sum){
if(qu.size() >= k && sum >= qu.top()) return; //
// cout << now <
if(now == n + 1) {
if(qu.size() < k)
qu.push(sum);
else {
if(qu.top() > sum) {
qu.pop(); qu.push(sum);
}
}
return;
}
for(int i = 0; i < ve[now].size(); i++){
int v = ve[now][i];
DFS(now + 1, sum + v);
}
}
int main(int argc, char **args){
// freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &k);
for(int i = 1; i <= n ;i++){
int m; scanf("%d", &m);
while(m--){
int a; scanf("%d", &a); ve[i].push_back(a);
}
sort(ve[i].begin(), ve[i].end());
}
DFS(1, 0);
int ans = 0;
while(k--){
// cout << qu.top() <
ans += qu.top(); qu.pop();
}
printf("%d
", ans);
return 0;
}
DP 코드
#include
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;
ll dp[N][2];
int main(int argc, char **args){
// freopen("in.txt", "r", stdin);
int n, k; scanf("%d%d", &n, &k);
int cur = 0; dp[0][cur ^ 1] = 1;
for(int i = 1; i <= n; i++){
int m; scanf("%d", &m);
for(int j = 0; j <= 10000; j++) dp[j][cur] = 0;
while(m--){
int a; scanf("%d", &a);
for(int j = 0; j <= 10000; j++){
if(dp[j][cur ^ 1] > 0)
dp[j + a][cur] += dp[j][cur ^ 1];
}
}
cur ^= 1;
}
cur ^= 1;
int ans = 0;
for(int i = 1; i <= 10000; i++){
if(k > 0) {
if(dp[i][cur] >= k) {
ans += k * i;
}else {
ans += dp[i][cur] * i;
}
k -= dp[i][cur];
}else break;
}
printf("%d
", ans);
return 0;
}
D
사고방식: 시합 때의 사고방식이 맞았는데 아쉽게도 버그를 발견하지 못했다.사실은 매우 간단하다. 이원조에서 삼원조로 가는 과정에서 우리는 계발을 얻을 수 있다.뒤에 m원조까지 확장되었는데 사실 본질은 모두 같다.dp[i][j]를 고려하면 위치 j로 시작한 i의 원조 개수를 나타낸다.전이 방정식: dp[i] [j] = ∑ak > a i & k > i dp [i -3 1] [k] dp[i] [j] =\sum{a k>a i\&k>i}dp[i-1][k]dp[i][j]=ak>ai&k>i ∑dp[i-3-1][k]는 어떻게 오른쪽 식을 구하는지 나무형 수조로 고려할 수 있습니다.트리 배열을 사용하려면 a i ai ai 값은 배열로 표시하지만 원래 a i ai ai의 값이 매우 커서 본 문제와 a i a 를 발견하였다iai는 본래 값과 상관없이 원소 간의 상대적인 크기가 변하지 않으면 되기 때문에 이산화한다.동시에 식자를 관찰하면 현재 층은 전 층의 값만 사용할 수 있기 때문에 스크롤 그룹을 이용하여 공간을 최적화할 수 있다.
코드:#include
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;
int n, m, nn;
int sum[N];
int c[N * 4], a[N];
void add(int pos, int x){
for(pos; pos > 0; pos -= (pos & -pos)){
c[pos] = (c[pos] + x) % MOD;
}
}
int query(int pos){
int sum = 0;
for(pos ; pos <= nn; pos += (pos & -pos)){
sum = (sum + c[pos]) % MOD;
}
return sum;
}
vector<int>ve;
int main(int argc, char **args){
// freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]); ve.push_back(a[i]);
}
sort(ve.begin(), ve.end());
ve.erase(unique(ve.begin(), ve.end()), ve.end());
for(int i = 1; i <= n; i++){
a[i] = lower_bound(ve.begin(), ve.end(), a[i]) - ve.begin() + 1; // ,
sum[i] = 1;//
}
nn = n * 2;
for(int j = 2; j <= m; j++){
memset(c, 0, sizeof(c));
for(int i = n; i > 0; i--){
add(a[i] , sum[i]);
sum[i] = query(a[i] + 1);
// cout << sum[i] <
}
}
if(m == 1){
cout << n <<"
";
}else {
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = (ans + sum[i]) % MOD;
}
printf("%d
", ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[NOIP2015 시뮬레이션 11.2만] 배미표
Description
Alice와 Bob, 아뇨, CZL과 YYY가 게임을 하고 있어요.책상 위에 n장의 카드가 있는데, 한 장의 카드는 두 사람에게 각각 유혹의 가치와 그 자신의 가치를 가지고 있다.CZL이 먼저 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;
int n, m, nn;
int sum[N];
int c[N * 4], a[N];
void add(int pos, int x){
for(pos; pos > 0; pos -= (pos & -pos)){
c[pos] = (c[pos] + x) % MOD;
}
}
int query(int pos){
int sum = 0;
for(pos ; pos <= nn; pos += (pos & -pos)){
sum = (sum + c[pos]) % MOD;
}
return sum;
}
vector<int>ve;
int main(int argc, char **args){
// freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]); ve.push_back(a[i]);
}
sort(ve.begin(), ve.end());
ve.erase(unique(ve.begin(), ve.end()), ve.end());
for(int i = 1; i <= n; i++){
a[i] = lower_bound(ve.begin(), ve.end(), a[i]) - ve.begin() + 1; // ,
sum[i] = 1;//
}
nn = n * 2;
for(int j = 2; j <= m; j++){
memset(c, 0, sizeof(c));
for(int i = n; i > 0; i--){
add(a[i] , sum[i]);
sum[i] = query(a[i] + 1);
// cout << sum[i] <
}
}
if(m == 1){
cout << n <<"
";
}else {
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = (ans + sum[i]) % MOD;
}
printf("%d
", ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[NOIP2015 시뮬레이션 11.2만] 배미표Description Alice와 Bob, 아뇨, CZL과 YYY가 게임을 하고 있어요.책상 위에 n장의 카드가 있는데, 한 장의 카드는 두 사람에게 각각 유혹의 가치와 그 자신의 가치를 가지고 있다.CZL이 먼저 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.