2019 항 전 다 교(제4 회)
http://acm.hdu.edu.cn/showproblem.php?pid=6614
제목
1-n 개 수 를 드 리 겠 습 니 다.
사고의 방향
사전 순서 가 가장 작 으 면 최소 위치 와 0 인 점 에서 찾 는 가장 작은 0 을 1 로 하면 전체 1 인 점 에 대해 100.0 에 연결 할 수 있다.
코드
#include
using namespace std;
int a[50];
int n;
int f[200005*2];
int ok(int x)
{
int qw;
int qwe = x;
for(int i = 1;i <= 18;i++)
{
a[i] = x % 2;
x /= 2;
if(a[i] == 1) qw = i;
}
int ans = 0;
x = 1;
for(int i = 1;i <= qw;i++)
{
if(a[i] == 0) {ans += x;break;}
x *= 2;
}
if(f[ans]) return 1;
if(ans == 0&&qwe + 1 <= n) return qwe+1;
else if(ans == 0) return 1;
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int x = 2;
int ans = 0;
for(int i = 1;;i++)
{
x *= 2;
if(x - 1 == n)
{
ans = 1;
break;
}
else if(x - 1 > n) break;
f[x-1] = 1;
}
printf("%d
",ans);
printf("1");
for(int i = 3;i <= n;i++)
{
ans = ok(i);
printf(" %d",ans);
}
printf("
");
}
return 0;
} 1003 Divide the Stones(사유)
http://acm.hdu.edu.cn/showproblem.php?pid=6616
제목
n 개 드릴 게 요.-n. 각 그룹의 숫자 와 같은 출력 분 법 을 k 조로 나 누 라 고 합 니 다.
사고의 방향
If the total number of stones is a multiple of k, we can always divide the stones. Otherwise, we can’t.
If n/k is even, you can find solution quite easily.
If n/k is an odd number, we divide first 3k stones into k groups with exactly 3 stones and equal weight.
After that, you can divide remaining stones by the way you did when n/k is even.
Time complexity is O(n).
코드
#include
using namespace std;
typedef long long ll;
const int maxn = 1e5+100;
vector ans[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ll n,k;
scanf("%lld%lld",&n,&k);
ll sum = n*(n+1)/2;
if(k == 1)
{
printf("yes
");
for(int i = 1;i <= n;i++)
{
printf("%d ",i);
}
continue;
}
if(sum % k != 0)
{
printf("no
");
continue;
}
ll qw = n / k;
printf("yes
");
for(int i = 1;i <= k;i++) ans[i].clear();
if(qw % 2 == 0)
{
int id = 1;
for(int i = 1;i <= n/2;i++)
{
ans[id].push_back(i);
id++;
if(id > k) id = 1;
}
id = 1;
for(int i = n;i > n/2;i--)
{
ans[id].push_back(i);
id++;
if(id > k) id = 1;
}
}
else
{
for(int i = 1; i <= k; i++)
{
ans[i].push_back(i);
ans[i].push_back(k + (i + k / 2 - 1) % k + 1);
ans[i].push_back(2 * k + (1 + k) / 2 * 3 - i - ((i + k / 2 - 1) % k + 1));
}
int len = (n-3*k) / 2;
int id = 1;
for(int i = 3*k+1;i <= 3*k+len;i++)
{
ans[id].push_back(i);
id++;
if(id > k) id = 1;
}
id = 1;
for(int i = n;i > 3*k+len;i--)
{
ans[id].push_back(i);
id++;
if(id > k) id = 1;
}
}
for(int i = 1;i <= k;i++)
{
for(int j = 0;j < ans[i].size();j++)
{
printf("%d ",ans[i][j]);
}
printf("
");
}
}
return 0;
}
1007 그냥 오래된 퍼 즐(정리)
http://acm.hdu.edu.cn/showproblem.php?pid=6620
제목
4*4 의 그림 을 드릴 게 요.120 걸음 안에 초기 상태 로 이동 할 수 있 냐 고.
사고의 방향
의 정리
4.567917.격자 열 수 는 홀수 이 고 아무리 이동 해도 원시 적 인 역순 수 를 바 꾸 지 않 는 다.홀수 가감 짝수 인지 홀수 인지 짝수 가감 짝수 인지 짝수 인지.따라서 역순 수가 짝수 라 는 것 만 확보 하면 되 며 빈 칸 의 위치 에 신경 쓰 지 않 아 도 된다
4.567917.격자 열 수 는 짝수 이 므 로 기 수 를 상하 로 이동 하면 역순 수의 짝수 성 을 바 꿀 수 있다.따라서 현재 역순 수가 짝수 라면 해 를 얻 으 려 면 실제 이동 에서 짝수 로 이동 할 수 있 도록 해 야 한다.즉,빈 칸 이 줄 에 있 는 것 과 초기 빈 칸 이 줄 에 있 는 차 이 는 짝수 라 는 것 이다
4.567917.같은 이치 로 현재 역순 수가 홀수 라면 풀 려 면 홀수 차례 의 이동 을 해 야 최종 역순 수가 짝수 임 을 보장 할 수 있다
코드
#include
using namespace std;
typedef long long ll;
int a[20];
int main()
{
int T;
scanf("%d",&T);
int p = 1;
while(T--)
{
p = 1;
for(int i = 1;i <= 4;i++)
{
for(int j = 1;j <= 4;j++)
{
int x;
scanf("%d",&x);
a[p++] = x;
}
}
if(a[16] != 0)
{
while(1)
{
for(int i = 1;i <= 16;i++)
{
if(a[i] == 0)
{
if(i + 4 <= 16)
{
swap(a[i],a[i+4]);
}
else
{
swap(a[i],a[i+1]);
}
}
}
if(a[16] == 0) break;
}
}
int num = 0;
for(int i = 1;i <= 15;i++)
{
for(int j = i + 1;j <= 15;j++)
{
if(a[i] > a[j]) num++;
}
}
if(num%2 == 0) printf("Yes
");
else printf("No
");
}
return 0;
} 1008 K-th 가장 가 까 운 거리(주석 트 리)
http://acm.hdu.edu.cn/showproblem.php?pid=6621
제목
n 개 수 를 몇 번 드릴 까요?
사고의 방향
강제 온라인 구간 문제 주석 트 리 2 분 답 조회 p-ans 에서 p+ans 범위 내 개수 가 k 보다 큰 지
코드
#include
#include
#include
using namespace std;
const int MAX = 1e5+100;
struct Node {
int sum, l, r;
} tree[MAX * 40];
int root[MAX], cnt;
int data[MAX];
int n,m;
// ID
//int get_id(int x) {
// return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
//}
void init() {
cnt = 0;
root[0] = 0;
}
//
int create_node(int po) {
int idx = ++cnt;
tree[idx].sum = tree[po].sum + 1;
tree[idx].l = tree[po].l;
tree[idx].r = tree[po].r;
return idx;
}
void updata(int &o, int po, int l, int r, int pos) {
o = create_node(po);
if (l == r) return;
int m = (l + r) >> 1;
if (pos <= m) updata(tree[o].l, tree[po].l, l, m, pos);
else updata(tree[o].r, tree[po].r, m + 1, r, pos);
}
//
//int query(int s, int e, int l, int r, int k) {
// if (l == r) return l;
// int m = (l + r) >> 1;
// int sum = tree[tree[e].l].sum - tree[tree[s].l].sum;
// if (k <= sum) return query(tree[s].l, tree[e].l, l, m, k);
// else return query(tree[s].r, tree[e].r, m + 1, r, k - sum);
//}
int query(int s,int e,int l,int r,int x,int y)
{
if(l == x&&r == y)
return tree[e].sum - tree[s].sum;
int mid = (l + r) / 2;
if(y <= mid) return query(tree[s].l,tree[e].l,l,mid,x,y);
else if(x > mid) return query(tree[s].r,tree[e].r,mid+1,r,x,y);
else return query(tree[s].l,tree[e].l,l,mid,x,mid) + query(tree[s].r,tree[e].r,mid+1,r,mid+1,y);
}
int main() {
int T;
scanf("%d",&T);
while(T--)
{
n = read(),m = read();
for(int i = 1;i <= n;i++)
{
scanf("%d",&data[i]);
// sorted.push_back(data[i]);
}
// sort(sorted.begin(),sorted.end());
// sorted.erase(unique(sorted.begin(),sorted.end()),sorted.end());
// int num = sorted.size();
init();
for(int i = 1;i <= n;i++)
{
updata(root[i],root[i-1],1,1e6,data[i]);
}
int qw = 0;
while(m--)
{
int l,r,p,k;
scanf("%d%d%d%d",&l,&r,&p,&k);
l ^= qw,r ^= qw,p ^= qw,k ^= qw;
if(l > r) swap(l,r);
int ll = 0,rr = max(p,(int)1e6-p);
while(ll + 1 < rr)
{
int mid = (ll + rr) / 2;
int num = query(root[l-1],root[r],1,1e6,max(p-mid,(int)1),min(p+mid,(int)1e6));
if(num >= k)
{
rr = mid;
}
else ll = mid;
}
int num = query(root[l-1],root[r],1,1e6,max(p-ll,(int)1),min(p+ll,(int)1e6));
if(num >= k)
{
printf("%d
",ll);
qw = ll;
}
else
{
printf("%d
",rr);
qw = rr;
}
}
}
return 0;
}
1010 프 라 임 의 최소한 의 힘(사유)
http://acm.hdu.edu.cn/showproblem.php?pid=6623
제목
숫자 n 드릴 게 요. 인수 분해 후 소수 의 모든 멱 중 가장 작은 것 이 얼마 인지 물 었 다.
사고의 방향
폭력 계산 n 의(1/5)차방 나머지 최대 5 차방 매 거 계산 을 초과 하지 않 으 면 됩 니 다.
코드
#include
using namespace std;
typedef long long ll;
const int N = 4000;
ll pri[N],top=0;
int vis[N];
ll po(ll a,int b)
{
ll ret=1;
while(b--)
ret*=a;
return ret;
}
int check(ll n,int k)
{
ll t=pow(n,1.0/k);
t-=5;
if(t<1)
t=1;
while(po(t+1,k)<=n)
t++;
return po(t,k)==n;
}
void solve(ll n)
{
int mi = 100000;
for(int i = 0;i < top&&pri[i] <= n;i++)
{
if(n % pri[i] == 0)
{
int num = 0;
while(n % pri[i] == 0)
{
num++;
n /= pri[i];
}
mi = min(mi,num);
}
}
if(n == 1) {printf("%d
",mi);return ;}
for(int i = 4;i >= 2;i--)
{
if(check(n,i))
{
printf("%d
",i);
return ;
}
}
printf("1
");
}
int main()
{
for(int i = 2;i <= N;i++)
{
if(vis[i] == 0)
{
pri[top++] = i;
for(int j = i+i;j <= N;j+=i)
{
vis[j] = 1;
}
}
}
int T;
scanf("%d",&T);
while(T--)
{
ll n;
scanf("%lld",&n);
solve(n);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
